Reverse Linked List

Problem

Reverse a linked list.

Example

For linked list 1->2->3, the reversed linked list is 3->2->1

Challenge

Reverse it in-place and in one-pass

Solution

A very basic linked list problem. Changing the direction of a node is simply updating the .next pointer, however the key to reverse the whole linked list is to use 3 pointers: prev, curr, and next. Pseudocode:

• while curr is not null:
  • next = curr.next: remember the next node.
  • curr.next = prev: reversing the direction. (The link to the next node is broken, that's why we need to remember it at the previous step.)
  • prev = curr: move prev forward to curr.
  • curr = next: move curr forward to next.

Pay attention to the order of the operations above, otherwise you may lose track of some of the nodes.

Language Specific Notes

Go

prev := nil will cause a compilation error (use of untyped nil in assignment). Use var prev *ListNode instead.