Reverse Linked List
EasyLinked lists
You get the head of a singly linked list. Reverse the list and return its new head.
Each node has a val and a next pointer, and the last node’s next is null. On this page a list is written as an array of its values, from head to tail.
Examples
Input: head = [1, 2, 3, 4] Output: [4, 3, 2, 1]
The links now run the other way, so 4 is the head.
Input: head = [7, 8] Output: [8, 7]
Two nodes swap places.
Constraints
- The list has 0 to 5000 nodes.
-5000 ≤ node.val ≤ 5000
Stuck?
Hint 1
Walk the list once and turn each next pointer around as you pass it. You need to remember the node before the current one.
Hint 2
Keep three names: previous, current, and the next node you are about to lose. Recursion works too, but it uses O(n) stack.
The idea
Walk the list once and turn each arrow around as you pass it. Three pointers are enough: the node behind, the node you are on, and the one ahead, which you save before changing the arrow that leads to it.
Time O(n)Extra space O(1)
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 5
previous starts as null because the first node becomes the last, and the last node points to nothing. current starts at the head.
function reverseList(head) { let previous = null; let current = head; while (current) { const next = current.next; current.next = previous; previous = current; current = next; } return previous;}The trap
Swapping only the first two nodes gives the right answer for a list of two, but every node after the second is cut off. Reversing has to turn every arrow, so it needs a loop over the whole list.
function reverseList(head) { if (!head || !head.next) return head; const second = head.next; second.next = head; // drops everything after the second node head.next = null; return second;}