🐟 Blog

Reverse Linked List

February 11, 2021

LeetCode

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

Β© Attribution Required | θ½¬θ½½θ―·ζ³¨ζ˜ŽεŽŸδ½œθ€…δΈŽζœ¬η«™ι“ΎζŽ₯
Β© 2021 yujinyan.me