Dashboard/Coding patterns/05. In-Place Manipulation of a Linked List

CODING PATTERNS · LESSON 5 OF 28 · 42 MIN VIDEO · 14 PROBLEMS

In-Place Manipulation of a Linked List

Module Progress (0 / 14 Problems Solved)0%
Coding patterns Track (0 / 28 Modules) · Overall 0/80 (0%)0%
⌁

Narrated HD Video Lesson (42 min) · Pro

Pattern Guide + Problem #01 + Checkpoint Quiz #1 are unlocked free below (no login required). Unlock all 80 HD video lessons and all 540 Python problems — or watch our two free sample video lessons first.

PATTERN STUDY GUIDE

In-Place Manipulation of a Linked List — How the Pattern Works

In-Place Manipulation of a Linked List restructures singly and circular linked lists directly by mutating .next pointers without allocating auxiliary arrays or duplicate nodes. Every link update preserves reachability through the atomic three-step sequence — save nxt = curr.next, rewire curr.next, and advance pointers — combined with sentinel (dummy) nodes when the head may change and two-pointer offsets for middle or tail discovery. This eliminates O(n) extra node/array memory and O(n^2) repeated traversals, executing reversals, deletions, splits, and interleavings in O(n) time and O(1) auxiliary space.

WHEN TO USE THIS PATTERN
  • Input is the head of a singly or circular linked list and the prompt mandates O(1) extra space or forbids modifying node .val fields and allocating new nodes.
  • Prompt asks to reverse an entire list, a [left, right] slice, fixed k-node groups, adjacent pairs, or conditional even-length groups.
  • Prompt asks to interleave, partition, split, or rotate a linked list by position (e.g., L_0 -> L_n -> L_1 -> L_{n-1}, odd-even positions, rotate right by k, split into k parts).
  • Prompt asks to remove duplicate values, filter matching elements, delete m-keep/n-drop runs, or splice a node into a sorted circular ring.
COMMON INTERVIEW PITFALLS
  • Overwriting curr.next before saving nxt = curr.next, permanently severing the only pointer path to the rest of the linked list.
  • Advancing prev immediately after deleting prev.next = prev.next.next — on consecutive target nodes (e.g., [6, 6] or [1, 1, 1]), moving prev skips testing the newly linked prev.next.
  • Forgetting to terminate split or rotated list tails with None (such as leaving slow.next connected in Reorder List or omitting new_tail.next = None in Rotate List), creating an infinite pointer cycle.
  • Handling head modifications with ad-hoc conditionals instead of prepending dummy = ListNode(0, head) and returning dummy.next, causing null-dereference bugs on empty or single-node inputs.
Three-Pointer Iterative ReversalReverse an entire singly linked list or an isolated segment in-place in O(n) time and O(1) space.
def reverse_list(head):
    prev, curr = None, head
    while curr:
        nxt = curr.next
        curr.next = prev
        prev, curr = curr, nxt
    return prev
Sentinel (Dummy) Head + Predecessor RewiringDelete, swap, or reverse sublists uniformly when the original head node itself may be removed or displaced.
def remove_matching(head, target):
    dummy = ListNode(0, head)
    prev = dummy
    while prev.next:
        if prev.next.val == target:
            prev.next = prev.next.next
        else:
            prev = prev.next
    return dummy.next
One-Pass Sublist Head InsertionReverse a contiguous slice right after prev in one pass by repeatedly detaching curr.next and inserting it at prev.next.
def reverse_slice_after(prev, moves):
    curr = prev.next
    for _ in range(moves):
        moved = curr.next
        curr.next = moved.next
        moved.next = prev.next
        prev.next = moved
🔒 PRO PROBLEMTarget: O(n + k) time · no new nodes

09. Split Linked List in Parts

Pattern Trigger: equal pieces → count, divide, then cut

Problem #01 of every pattern lesson is unlocked free outside the paywall. Unlock all 540 Python 3.14 problems, step-by-step solution editorials, and 80 narrated HD video lessons with Monthly ($69), 3-Month ($149), or Annual ($299) access — or 50% off for verified university students.

Pattern Checkpoint Quizzes

CHECKPOINT QUIZ #1

You're about to flip one arrow. Which step has to come first?