Linked List Reversal: Templates for Three Scenarios

Core Operation of Reversal

The fundamental unit of reversal is "pointing cur.next to prev":

Before: prev → cur → next → ...
After:  prev ← cur   next → ...

Reverse Entire List (LeetCode 206)

Iterative (Recommended)

ListNode reverseList(ListNode head) {
    ListNode prev = null, cur = head;
    while (cur != null) {
        ListNode nextTemp = cur.next;   // Save successor
        cur.next = prev;                // Reverse pointer
        prev = cur;                     // Advance pointers
        cur = nextTemp;
    }
    return prev;   // The new head
}

{
  "type": "linked-list",
  "title": "Reverse Linked List 1→2→3→4→5",
  "steps": [
    {
      "note": "Initial state: prev=null, cur=1",
      "listNodes": [
        {"id": 0, "val": 1, "next": 1},
        {"id": 1, "val": 2, "next": 2},
        {"id": 2, "val": 3, "next": 3},
        {"id": 3, "val": 4, "next": 4},
        {"id": 4, "val": 5, "next": null}
      ],
      "activeNode": 0
    },
    {
      "note": "1.next = null (Reversed direction), prev=1, cur=2",
      "listNodes": [
        {"id": 0, "val": 1, "next": null},
        {"id": 1, "val": 2, "next": 2},
        {"id": 2, "val": 3, "next": 3},
        {"id": 3, "val": 4, "next": 4},
        {"id": 4, "val": 5, "next": null}
      ],
      "activeNode": 1
    },
    {
      "note": "2.next = 1 (Reversed direction), prev=2, cur=3",
      "listNodes": [
        {"id": 0, "val": 1, "next": null},
        {"id": 1, "val": 2, "next": 0},
        {"id": 2, "val": 3, "next": 3},
        {"id": 3, "val": 4, "next": 4},
        {"id": 4, "val": 5, "next": null}
      ],
      "activeNode": 2
    },
    {
      "note": "3.next=2, 4.next=3, 5.next=4. Completed, new head=5",
      "listNodes": [
        {"id": 0, "val": 1, "next": null},
        {"id": 1, "val": 2, "next": 0},
        {"id": 2, "val": 3, "next": 1},
        {"id": 3, "val": 4, "next": 2},
        {"id": 4, "val": 5, "next": 3}
      ],
      "activeNode": 4
    }
  ]
}

Recursive (Understanding Recursive Logic)

ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) return head;  // Last node becomes the new head
    ListNode newHead = reverseList(head.next);   // Recursively reverse sub-list
    head.next.next = head;                       // Make the next node point back to 'current'
    head.next = null;                            // Disconnect the old forward pointer
    return newHead;
}

The recursive approach reverses the list from the end forward, propagating the new head back up the stack.

Reverse First N Nodes

ListNode successor = null;  // To track the (N+1)-th node

ListNode reverseN(ListNode head, int n) {
    if (n == 1) {
        successor = head.next;   // The (N+1)-th node where the tail should connect
        return head;
    }
    ListNode newHead = reverseN(head.next, n - 1);
    head.next.next = head;
    head.next = successor;       // Connect the reversed part to the rest of the list
    return newHead;
}

Reverse Range [left, right] (LeetCode 92)

Find the (left-1)-th node, reverse the next (right-left+1) nodes, and then reconnect the segments:

ListNode reverseBetween(ListNode head, int left, int right) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode pre = dummy;

    // Move 'pre' to the (left-1)-th position
    for (int i = 1; i < left; i++) pre = pre.next;

    // Use "Insertion Method" to reverse the next (right - left) nodes
    ListNode cur = pre.next;
    for (int i = 0; i < right - left; i++) {
        ListNode next = cur.next;
        cur.next = next.next;
        next.next = pre.next;
        pre.next = next;
    }
    return dummy.next;
}

The Insertion Method is a popular trick for range reversal: in each iteration, you take the node after cur and move it to the position immediately after pre. This avoids the need for an extra prev pointer.

Reverse Nodes in k-Group (LeetCode 25)

Check if there are at least k nodes remaining; if so, reverse them; otherwise, keep them as is.

ListNode reverseKGroup(ListNode head, int k) {
    // Check if there are at least k nodes left
    ListNode tail = head;
    for (int i = 0; i < k; i++) {
        if (tail == null) return head;   // Fewer than k nodes, return as is
        tail = tail.next;
    }
    // Reverse these k nodes
    ListNode newHead = reverse(head, tail);
    // Recursively handle the next part and connect to the current tail (original head)
    head.next = reverseKGroup(tail, k);
    return newHead;
}

// Helper to reverse the range [head, tail)
ListNode reverse(ListNode head, ListNode tail) {
    ListNode prev = null, cur = head;
    while (cur != tail) {
        ListNode nextTemp = cur.next;
        cur.next = prev;
        prev = cur;
        cur = nextTemp;
    }
    return prev;
}

Summary