In-place Reversal of Linked List
1. Reverse Linked List In-place O(1) Space
| Approach | Technique | Time | Space |
|---|---|---|---|
| Iterative Three Pointers | prev, curr, next - reverse links one by one | O(n) |
O(1) |
| Recursive | Reverse rest, then fix current node's pointers | O(n) |
O(n) stack |
| Tail Recursive | Pass reversed portion as accumulator | O(n) |
O(n) stack |
| Stack-based | Push all nodes, pop and reconnect | O(n) |
O(n) |
Example: Reverse entire linked list iteratively
class ListNode {
constructor(val = 0, next = null) {
this.val = val;
this.next = next;
}
}
function reverseList(head) {
let prev = null;
let curr = head;
while (curr !== null) {
const next = curr.next; // Save next node
curr.next = prev; // Reverse current link
prev = curr; // Move prev forward
curr = next; // Move curr forward
}
return prev; // New head
}
// Example: 1->2->3->4->5
// Step by step:
// Initial: null <- prev, 1->2->3->4->5 (curr at 1)
// After 1: null <- 1, prev=1, curr=2
// After 2: null <- 1 <- 2, prev=2, curr=3
// Final: 5->4->3->2->1->null2. Reverse Linked List Sublist Pattern
| Step | Action | Purpose | Pointer Updates |
|---|---|---|---|
| 1. Navigate to Start | Move to node before reversal position | Keep reference to connection point | prev pointer to (m-1)th node |
| 2. Reverse Sublist | Reverse nodes from position m to n | Flip links in specified range | Standard three-pointer reversal |
| 3. Reconnect | Connect pre-reversed and post-reversed parts | Maintain list integrity | Fix head and tail connections |
| Dummy Head | Use dummy node to handle edge cases | Simplify when m=1 (reversing from head) | Always have node before start |
Example: Reverse between positions m and n
function reverseBetween(head, left, right) {
if (!head || left === right) return head;
const dummy = new ListNode(0, head);
let prev = dummy;
// Move to node before left position
for (let i = 1; i < left; i++) {
prev = prev.next;
}
// Reverse the sublist
let curr = prev.next;
let next = null;
for (let i = 0; i < right - left; i++) {
next = curr.next;
curr.next = next.next;
next.next = prev.next;
prev.next = next;
}
return dummy.next;
}
// Example: 1->2->3->4->5, left=2, right=4
// Result: 1->4->3->2->5
// Alternative approach with standard reversal:
function reverseBetweenStandard(head, left, right) {
if (!head || left === right) return head;
const dummy = new ListNode(0, head);
let preReverse = dummy;
// Navigate to node before reversal
for (let i = 1; i < left; i++) {
preReverse = preReverse.next;
}
// Reverse sublist
let prev = null;
let curr = preReverse.next;
const tail = curr; // Will become tail after reversal
for (let i = 0; i <= right - left; i++) {
const next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
// Reconnect
preReverse.next = prev; // Connect to new head of reversed
tail.next = curr; // Connect tail to remainder
return dummy.next;
}3. Reverse Nodes in K-Group
| Challenge | Solution | Edge Case | Complexity |
|---|---|---|---|
| Group Identification | Check if k nodes remaining before reversing | Last group with < k nodes stays as is | Count ahead k nodes |
| Group Reversal | Reverse exactly k nodes at a time | Use counter, not null check | O(k) per group |
| Connection Management | Track prev group's tail, current group's head/tail | First group becomes new head | Careful pointer tracking |
| Recursion Alternative | Reverse current group, recurse for rest | Elegant but uses stack space | O(n/k) stack |
Example: Reverse nodes in k-group
function reverseKGroup(head, k) {
// Check if we have k nodes
let count = 0;
let curr = head;
while (curr && count < k) {
curr = curr.next;
count++;
}
if (count < k) {
return head; // Not enough nodes, return as is
}
// Reverse k nodes
let prev = null;
curr = head;
for (let i = 0; i < k; i++) {
const next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
// prev is new head, head is now tail, curr is next group
head.next = reverseKGroup(curr, k); // Recurse for rest
return prev;
}
// Example: 1->2->3->4->5, k=2
// Result: 2->1->4->3->5
// Example: 1->2->3->4->5, k=3
// Result: 3->2->1->4->5 (last 2 nodes unchanged)Example: Reverse k-group iteratively
function reverseKGroupIterative(head, k) {
const dummy = new ListNode(0, head);
let prevGroupTail = dummy;
while (true) {
// Check if k nodes available
let kthNode = prevGroupTail;
for (let i = 0; i < k; i++) {
kthNode = kthNode.next;
if (!kthNode) return dummy.next;
}
const nextGroupHead = kthNode.next;
// Reverse current group
let prev = nextGroupHead;
let curr = prevGroupTail.next;
for (let i = 0; i < k; i++) {
const next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
// Connect reversed group
const newGroupTail = prevGroupTail.next;
prevGroupTail.next = prev; // Connect to new head
prevGroupTail = newGroupTail; // Move to next group
}
}
// Iterative version avoids recursion stack
// More complex pointer management but O(1) space4. Rotate Linked List Pattern
| Step | Operation | Formula | Edge Case |
|---|---|---|---|
| 1. Find Length | Count all nodes, get tail | n = length |
Empty list or single node |
| 2. Normalize k | Handle k > n | k = k % n |
k = 0 or k = n (no rotation) |
| 3. Find Break Point | Navigate to (n-k)th node | newTail = node at (n-k-1) |
Becomes new tail |
| 4. Rotate | Make circular, break at new tail | tail.next = head; newTail.next = null |
Return new head |
Example: Rotate list right by k places
function rotateRight(head, k) {
if (!head || !head.next || k === 0) {
return head;
}
// Find length and tail
let length = 1;
let tail = head;
while (tail.next) {
tail = tail.next;
length++;
}
// Normalize k
k = k % length;
if (k === 0) {
return head; // No rotation needed
}
// Find new tail (at position n - k - 1)
let newTail = head;
for (let i = 0; i < length - k - 1; i++) {
newTail = newTail.next;
}
// Perform rotation
const newHead = newTail.next;
newTail.next = null; // Break the list
tail.next = head; // Connect old tail to old head
return newHead;
}
// Example: 1->2->3->4->5, k=2
// Result: 4->5->1->2->3
// Steps:
// 1. length=5, tail=5
// 2. k=2 (already < 5)
// 3. newTail = node at position 2 (value 3)
// 4. newHead = 4, break at 3, connect 5->1
// Result: 4->5->1->2->3
Note: Rotation is essentially moving last k nodes to front. Key insight: make list circular temporarily, then break at correct position. Always normalize k with modulo to handle k > n.
5. Swap Nodes in Pairs (Linked List)
| Approach | Method | Complexity | Key Pointer |
|---|---|---|---|
| Iterative Swap | Swap adjacent pairs, update pointers | O(n) time, O(1) space |
Track prev, first, second of each pair |
| Recursive | Swap current pair, recurse for rest | O(n) time, O(n) space |
Clean but uses stack |
| Dummy Head | Use dummy to simplify edge cases | Recommended pattern | Handles first pair uniformly |
| Value Swap | Swap values instead of nodes | Simple but not true in-place | Not recommended for interviews |
Example: Swap pairs iteratively
function swapPairs(head) {
const dummy = new ListNode(0, head);
let prev = dummy;
while (prev.next && prev.next.next) {
const first = prev.next;
const second = prev.next.next;
// Swap the pair
prev.next = second;
first.next = second.next;
second.next = first;
// Move to next pair
prev = first;
}
return dummy.next;
}
// Example: 1->2->3->4
// Result: 2->1->4->3
// Step by step:
// Initial: dummy->1->2->3->4
// Swap 1,2: dummy->2->1->3->4
// Swap 3,4: dummy->2->1->4->3Example: Swap pairs recursively
function swapPairsRecursive(head) {
// Base case: no node or single node
if (!head || !head.next) {
return head;
}
const first = head;
const second = head.next;
// Swap current pair
first.next = swapPairsRecursive(second.next);
second.next = first;
return second; // New head of this pair
}
// Recursive solution is elegant:
// 1. Swap current pair
// 2. Recurse for rest
// 3. Connect first to result of recursion
// 4. Return second as new head
// Example trace for 1->2->3->4:
// swap(1->2->3->4)
// swap(3->4) returns 4->3
// 1.next = 4->3
// 2.next = 1
// returns 2
// Result: 2->1->4->3Example: General swap every k nodes
// Extension: Swap every k nodes (generalization)
function swapKNodes(head, k) {
if (k <= 1) return head;
const dummy = new ListNode(0, head);
let prev = dummy;
while (true) {
// Check if k nodes available
let check = prev;
for (let i = 0; i < k; i++) {
check = check.next;
if (!check) return dummy.next;
}
// Reverse k nodes
let curr = prev.next;
let tail = curr;
let p = null;
for (let i = 0; i < k; i++) {
const next = curr.next;
curr.next = p;
p = curr;
curr = next;
}
// Connect reversed group
prev.next = p;
tail.next = curr;
prev = tail;
}
}
// For k=2, this is same as swapPairs
// For k=3, swaps every 3 nodes
// Similar to reverse k-group but simpler (always reverse)Summary: In-place Reversal Patterns
- Basic Reversal: Three pointers (prev, curr, next) - save next, reverse link, advance all pointers - O(n) time, O(1) space
- Dummy Node: Essential for in-place reversal problems - eliminates edge cases for reversing from head
- Reverse Sublist: Navigate to start-1, reverse m to n nodes, reconnect - can use one-shot or standard reversal approach
- One-shot Reversal: Move nodes one by one to front of sublist:
next.next = prev.next; prev.next = next - Standard Reversal: Reverse sublist with prev/curr/next, save original tail, reconnect both ends
- Reverse K-Group: Check k nodes exist, reverse exactly k nodes, recurse or iterate - last incomplete group stays unchanged
- Iterative K-Group: O(1) space but complex pointer management - track prevGroupTail, reverse group, connect, advance
- Rotate List: Find length and tail, normalize k with modulo, find new tail at (n-k-1), make circular then break
- Swap Pairs: Special case of k=2, swap adjacent pairs - iterative with dummy or elegant recursive
- Pointer Pattern: prev points to node before operation, first/second for pairs, tail for reconnection
- Common Edge Cases: Empty list, single node, k>n, k=0, odd number of nodes
- Space Trade-off: Iterative O(1) vs recursive O(n) stack - prefer iterative for production, recursive for clarity