templates · Linked lists, sorting & selection

Reverse a linked list

  • "Reverse" the list, or a part of it (positions left..right, every k nodes)
  • You must change the order in place, with O(1) extra memory
  • A step of a bigger problem: palindrome check, reorder list

In-place linked-list rewiring

the one rule

The invariant

prev is the head of the already-reversed part, and cur is the head of the part not touched yet.

write it from memory

The template

reverse the whole list

javajava.util.*
/** Reverse the whole list. Three pointers: prev, cur, next. */static ListNode reverse(ListNode head) {    ListNode prev = null;                    // the reversed part so far    ListNode cur = head;    while (cur != null) {        ListNode next = cur.next;            // save the rest before we cut        cur.next = prev;                     // flip one arrow        prev = cur;                          // step both pointers forward        cur = next;    }    return prev;                             // prev is the new head}

Save, flip, step. Bas itna yaad rakho: save next before you change cur.next, or the rest of the list is lost.

fill in the blanks — only these lines change per problem

  1. line 5When to stop. For "reverse k nodes", stop after k steps instead of at null.
  2. line 11What to return: the new head prev, or reconnect the reversed part to the rest first.

reverse positions left..right

javajava.util.*
/** Reverse only positions left..right (1-based). A dummy node makes left = 1 the same as any other case. */static ListNode reverseBetween(ListNode head, int left, int right) {    ListNode dummy = new ListNode(0, head);    ListNode before = dummy;    for (int i = 1; i < left; i++) before = before.next;   // node just before the part    ListNode tail = before.next;             // becomes the tail of the reversed part    for (int i = 0; i < right - left; i++) { // move each next node to the front        ListNode moved = tail.next;        tail.next = moved.next;        moved.next = before.next;        before.next = moved;    }    return dummy.next;}

A dummy node in front of the head means reversing from position 1 needs no special case.

fill in the blanks — only these lines change per problem

  1. line 5How far to walk before you start: to the node just before position left.
  2. line 7How many nodes to move to the front: right - left of them.

complexity

What it costs

time O(n)
Each node is visited once and its next arrow is flipped once.
space O(1)
Only a few pointers. No new nodes, no stack, no recursion.

watch out

Common bugs

  • Writing cur.next = prev before saving cur.next. The rest of the list is gone.
  • Returning head instead of prev. After the loop, the old head is the new tail.
  • No dummy node, so reversing from position 1 needs messy if checks and often breaks.

use it

Practise it on

learn it properly