Reverse a Linked List

Share

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

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

Contents

Solution 1 - Iterative Approach

The key idea is to traverse the list and reverse the next pointer of each node to point to its previous node. We maintain three pointers: prev, curr, and next.

  • Initialize prev = null and curr = head.
  • While curr is not null, save curr.next in a temporary variable, then point curr.next to prev.
  • Advance prev to curr and curr to the saved next node.
  • After the loop, prev is the new head of the reversed list.
Java
class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class ReverseLinkedList {

    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next; // save next
            curr.next = prev;          // reverse pointer
            prev = curr;               // move prev forward
            curr = next;               // move curr forward
        }
        return prev; // prev is now the new head
    }
}
Complexity Analysis:

Time complexity: O(n) where n is the number of nodes in the linked list, since we visit each node once.
Space complexity: O(1) as we only use a constant number of pointers.

Solution 2 - Recursive Approach

In the recursive approach, we recurse to the end of the list and then fix the pointers on the way back.

  • Base case: if head == null or head.next == null, return head (it is the new head).
  • Recursively reverse the rest of the list starting from head.next.
  • After the recursive call returns, head.next is the last node of the reversed sublist. Set head.next.next = head to make it point back to the current node.
  • Set head.next = null to avoid a cycle and return the new head.
Java
public class ReverseLinkedList {

    public ListNode reverseListRecursive(ListNode head) {
        // Base case: empty list or single node
        if (head == null || head.next == null) {
            return head;
        }
        // Reverse the rest of the list
        ListNode newHead = reverseListRecursive(head.next);
        // Make head.next point back to head
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}
Complexity Analysis:

Time complexity: O(n) since every node is visited exactly once through the recursion.
Space complexity: O(n) due to the recursion call stack, which can go n levels deep.