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->null
2. Reverse 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 K Group Nodes
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) space
4. Rotate 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
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->3
Example: 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->3
Example: 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