Reverse a Linked List

LeetCode 206 · View on LeetCode

Use three pointers: prev, curr, and next. Walk through the list, flipping each node's Next pointer to point backward. When curr reaches nil, prev is the new head.

package main

import "fmt"

type ListNode struct {
	Val  int
	Next *ListNode
}

func reverseList(head *ListNode) *ListNode {
	var prev *ListNode
	curr := head
	for curr != nil {
		next := curr.Next
		curr.Next = prev
		prev = curr
		curr = next
	}
	return prev
}

func printList(head *ListNode) {
	for curr := head; curr != nil; curr = curr.Next {
		fmt.Print(curr.Val, " -> ")
	}
	fmt.Println("nil")
}

func main() {
	head := &ListNode{1, &ListNode{2, &ListNode{3, &ListNode{4, &ListNode{5, nil}}}}}
	printList(head)          // 1 -> 2 -> 3 -> 4 -> 5 -> nil
	head = reverseList(head)
	printList(head)          // 5 -> 4 -> 3 -> 2 -> 1 -> nil
}