Reverse Linked List

Feb 11, 2021

easy

Given the head of a singly linked list, reverse the list, and return the reversed list.

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Recursive Method

public ListNode reverse(ListNode node) {
  if (node == null || node.next == null) {
    return node;
  }
  ListNode newHead = reverse(node.next); 
  node.next.next = node;
  node.next = null;
  return newHead;
}

Recursive call trace:

┌ reverse (1) -> 2 -> 3 -> 4 -> 5
│ ┌ reverse 1 -> (2) -> 3 -> 4 -> 5
│ │ ┌ reverse 1 -> 2 -> (3) -> 4 -> 5
│ │ │ ┌ reverse 1 -> 2 -> 3 -> (4) -> 5
│ │ │ │  reverse 1 -> 2 -> 3 -> 4 -> (5)
│ │ │ └ reverse 1 -> 2 -> 3 -> (4) <~ 5
│ │ └ reverse 1 -> 2 -> (3) <~ 4 <~ 5
│ └ reverse 1 -> (2) <~ 3 <~ 4 <~ 5
└ reverse (1) <~ 2 <~ 3 <~ 4 <~ 5

Note in this example:

The recursive reverse call corresponds to the highlighted portion in the run-time call trace.
newHead is always $5$ .