# Reverse Linked List

February 11, 2021

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$.

Β© Attribution Required | θ½¬θ½½θ―·ζ³¨ζεδ½θδΈζ¬η«ιΎζ₯
Β© 2022 yujinyan.me