Reverse Linked List


Reverse a linked list.


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


Reverse it in-place and in one-pass


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


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

Online Judge