Interview
Interview Guide
Coding Problems List
Problems

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.