Reverse Linked List
easy | Accept. 71% | εζ£δΈζη«
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(head.next); node.next.next = head;
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:
newHead
is always .