Linked lists are often introduced as one of the simplest data structures: 2 → 5 → 7 → 11 → None

Each node contains some data and a pointer to the next node. Simple, right? Yet linked-list problems are among the best tests of whether a candidate truly understands:

references
pointer manipulation
invariants
edge cases
memory usage
structural transformations

The algorithms themselves are usually not mathematically complicated. The difficulty is rewiring references without losing the structure. That is the central lesson of Part 7 — Linked Lists.

Linked-list problems are primarily about pointer manipulation + invariants + careful edge-case handling.

The Part progresses through 13 problems, beginning with merging and reversing lists and gradually moving into cycles, overlapping lists, pointer gaps, rotations, partitioning, palindromes, and arbitrary-precision arithmetic.

1. What Part 7 Is Really Teaching

Don’t approach this Part as:

“I need to memorize 13 linked-list solutions.”

Instead, build a small set of reusable patterns. LINKED LISTS │ ┌──────────────────┼──────────────────┐ │ │ │ ▼ ▼ ▼ Traversal Pointer Rewiring Fast / Slow │ │ │ ▼ ▼ ▼ Merge Reverse Cycle Delete Sublist Reverse Middle Rotate │ ▼ Two-Pointer Gap │ ▼ kth-from-last

Advanced Families │ ┌──────────┴──────────┐ ▼ ▼ Intersection Cycles │ │ ▼ ▼ Length Alignment Case Analysis │ ▼ Arithmetic

The 13 problems are really variations of these patterns.

2. Linked-List Fundamentals

A singly linked-list node can be represented as: class ListNode: def __init__(self, data=0, next_node=None): self.data = data self.next = next_node

A list: 2 → 5 → 7 → 11 → None

can be visualized as: head ↓ [2 | •] → [5 | •] → [7 | •] → [11 | None]

Each node knows only about the next node. That single property creates most of the algorithmic challenges we’ll encounter.

3. Array vs Linked List

This distinction should be automatic in an interview.

Operation	Array	Singly Linked List
Access kth element	O(1)	O(n)
Search	O(n)	O(n)
Insert at beginning	O(n) typically	O(1)
Delete after known node	O(n)	O(1)
Reverse	O(n)	O(n)
Find middle	Indexing	Fast/slow
Random access	Excellent	Poor
Memory locality	Excellent	Poor

The central trade-off is: Array → fast random access

Linked List → efficient local pointer manipulation

A linked list is not “better” or “worse” than an array. It is optimized for a different access pattern.

4. The First Major Pattern: Dummy Nodes

One of the most useful techniques in linked-list interviews is the dummy/sentinel node. Suppose: head → 2 → 3 → 5

and you need to delete the head. The head has no predecessor. That creates a special case. Instead: dummy → head → 2 → 3 → 5

Now every real node has a predecessor. This dramatically simplifies:

insertion
deletion
merging
kth-last deletion
partitioning
even/odd merging

Typical setup: dummy = ListNode(0, head)

Interview rule

Whenever a linked-list problem involves:

“The head may change.”

Immediately consider a dummy node. This small technique eliminates a surprisingly large number of edge-case bugs.

5. Pointer Rewiring: The Fundamental Skill

Most linked-list algorithms eventually modify: node.next

The danger is that changing next too early can cause you to lose the rest of the list. For example, during reversal: next_node = current.next current.next = previous

previous = current current = next_node

The order matters. First save: next_node = current.next

Then modify: current.next = previous

Then advance. This simple pattern is the foundation of linked-list reversal and many other pointer algorithms.

6. The 13 Problems in Part 7

Problem	Core Technique
7.1	Merge Two Sorted Lists
7.2	Reverse a Sublist
7.3	Detect Cycle
7.4	Overlapping Lists — No Cycle
7.5	Overlapping Lists — Possible Cycles
7.6	Delete Node in O(1)
7.7	Remove kth-Last Element
7.8	Remove Duplicates
7.9	Cyclic Right Shift
7.10	Even-Odd Merge
7.11	Linked-List Palindrome
7.12	List Pivoting
7.13	Add List-Based Integers

The key is not to learn 13 separate algorithms. It’s to recognize the smaller number of techniques behind them.

7. Merge Two Sorted Lists

This is one of the most important basic linked-list problems. Given: L1: 2 → 5 → 7

L2: 3 → 11

produce: 2 → 3 → 5 → 7 → 11

Because both lists are already sorted, we don’t need to concatenate and sort. Instead, maintain two pointers: p1 → L1 p2 → L2

At every step:

Take the smaller current node.

This produces a sorted merged prefix.

Python Implementation

def merge_two_sorted_lists(L1, L2): dummy = ListNode() tail = dummy

while L1 and L2: if L1.data < L2.data: tail.next = L1 L1 = L1.next else: tail.next = L2 L2 = L2.next

tail = tail.next

tail.next = L1 or L2

return dummy.next

Complexity: Time: O(n + m) Space: O(1)

The existing nodes are reused. The dummy node also removes the special case for creating the first node.

8. Reverse a Single Sublist

Suppose: 1 → 2 → 3 → 4 → 5

and we need to reverse positions 2 through 4. Result: 1 → 4 → 3 → 2 → 5

The requirement is important:

Don’t allocate additional nodes.

The correct approach is:

Find the node before the sublist.
Reverse links inside the sublist.
Reconnect the reversed section.

A dummy node makes this much easier.

Python

def reverse_sublist(head, start, finish): dummy = ListNode(0, head)

sublist_head = dummy

for _ in range(1, start): sublist_head = sublist_head.next

sublist_iter = sublist_head.next

for _ in range(finish - start): temp = sublist_iter.next

sublist_iter.next = temp.next temp.next = sublist_head.next sublist_head.next = temp

return dummy.next

The inner operation repeatedly moves the next node to the front of the sublist. For: A → B → C → D

we transform: A → B → D

and insert C before B: A → C → B → D

Repeatedly applying this produces the reversed section. Complexity: Time: O(f) Space: O(1)

where f is the ending position.

9. Cycle Detection: Fast and Slow Pointers

Consider: 1 → 2 → 3 → 4 → None

No cycle. But: 1 → 2 → 3 → 4 ↑ | └─────┘

contains a cycle. A naive solution uses a set of visited nodes: visited = set()

This gives: Time: O(n) Space: O(n)

But we can do better.

10. Floyd’s Cycle Detection

Use two pointers: slow → one step fast → two steps

slow = slow.next fast = fast.next.next

If a cycle exists, eventually: slow is fast

Why? Imagine the cycle as a circular track. Slow moves one node per iteration. Fast moves two. Therefore fast gains one node per iteration relative to slow. Inside a finite cycle, fast eventually catches slow. Complexity: Time: O(n) Space: O(1)

11. Finding the Cycle Start

Detecting a cycle is only half the problem. After: slow == fast

we still need to determine where the cycle begins. One approach is:

Determine cycle length.
Put two pointers at the head.
Move one pointer ahead by the cycle length.
Move both together.
They meet at the cycle start.

Python: def has_cycle(head): slow = fast = head

while fast and fast.next: slow = slow.next fast = fast.next.next

if slow is fast: break else: return None

cycle_len = 1 p = slow.next

while p is not slow: p = p.next cycle_len += 1

p1 = head p2 = head

for _ in range(cycle_len): p2 = p2.next

while p1 is not p2: p1 = p1.next p2 = p2.next

return p1

The key invariant is:

p2 is exactly cycle_len nodes ahead of p1****.

That invariant is what guarantees they meet at the cycle beginning.

12. Overlapping Lists Without Cycles

Suppose two lists eventually converge: L1: A → B \ C → D → E / L2: X → Y

They overlap when they share the same node object. Not merely the same value. This distinction is critical. node1.data == node2.data

does not imply: node1 is node2

Node identity matters.

13. Length Alignment

If two cycle-free lists overlap, once they converge they cannot diverge again. Why? Because each node has exactly one next. Therefore, overlapping lists must have the same tail. Suppose: L1 length = 7 L2 length = 5

Advance L1 by: 7 - 5 = 2

nodes. Now both pointers have the same number of nodes remaining. Then: while p1 is not p2: p1 = p1.next p2 = p2.next

The first identity match is the intersection point. Complexity: Time: O(n + m) Space: O(1)

This is a beautiful example of using structure rather than extra memory.

14. Overlapping Lists With Cycles

This is one of the hardest problems in the Part. Now each list can be: acyclic

or: cyclic

The correct strategy is case analysis. First determine the cycle start for each list: root1 root2

Then there are three major cases.

Case 1 — Neither Has a Cycle

Use the ordinary overlap algorithm.

Case 2 — Exactly One Has a Cycle

They cannot overlap. Why? If an acyclic list entered a cycle, it would become cyclic itself. Therefore: return None

Case 3 — Both Have Cycles

Now determine whether their cycles are the same. Starting from root1, walk around its cycle. If you encounter root2, both lists share the same cycle. If you return to root1 without encountering root2, the cycles are disjoint. This decomposition is much easier to reason about than trying to solve every possibility simultaneously.

15. Delete a Node in O(1)

This is a famous interview puzzle. Suppose: A → B → C → D

and you’re given a pointer to B, but not the head. Normally, deleting B requires: A.next = C

But you don’t have A. The trick is to copy the successor’s data: A → C → C → D

Then skip the successor: A → C → D

Python: def delete_node(node): node.data = node.next.data node.next = node.next.next

Complexity: Time: O(1) Space: O(1)

Critical limitation

The node cannot be the tail. If: A → B → None

there is no successor from which to copy data.

16. The Staff-Level Caveat

In a textbook, copying the successor’s data is fine. In a real system, a node might contain: Node { id metadata children external references }

Blindly copying the entire payload might have semantic consequences. A Staff-level engineer should ask:

“Is copying this node’s data semantically equivalent to deleting the original node?”

This is the difference between solving the puzzle and understanding the engineering implications.

17. Remove the kth-Last Element

Given: 1 → 2 → 3 → 4 → 5

remove the second-last element: 1 → 2 → 3 → 5

The interesting requirement is:

Do it without first computing the length.

Use two pointers separated by a fixed gap. first –––––––– k –––––––– second

Move first ahead by k. Then move both pointers together. When first reaches the end, second is positioned just before the node to delete. Python: def remove_kth_last(L, k): dummy = ListNode(0, L)

first = dummy.next

for _ in range(k): first = first.next

second = dummy

while first: first = first.next second = second.next

second.next = second.next.next

return dummy.next

Complexity: Time: O(n) Space: O(1)

The reusable pattern is:

Fixed-gap two pointers.

It appears in:

kth node from end
middle node
cycle-related problems
sliding-window-style linked structures

18. Remove Duplicates From a Sorted List

Given: 2 → 2 → 3 → 5 → 5 → 7 → 11 → 11

produce: 2 → 3 → 5 → 7 → 11

The important clue is:

The list is sorted.

Therefore duplicates are adjacent. We don’t need a hash set. Instead, scan consecutive nodes and skip equal values. def remove_duplicates(head): current = head

while current: next_distinct = current.next

while ( next_distinct and next_distinct.data == current.data ): next_distinct = next_distinct.next

current.next = next_distinct current = next_distinct

return head

Although there is a nested loop, the total work is: O(n)

because each link is traversed only a constant number of times. The broader lesson: Unsorted → hash set

Sorted → adjacent scan

Always exploit structural properties in the input.

19. Cyclic Right Shift

Given: 1 → 2 → 3 → 4 → 5

shift right by 2: 4 → 5 → 1 → 2 → 3

Repeatedly shifting one node at a time would cost: O(nk)

Instead: k %= n

because shifting by n changes nothing. The elegant trick is:

Find the length.
Connect the tail to the head.
Find the new tail.
Break the cycle.

def cyclic_right_shift(head, k): if not head or not head.next or k == 0: return head

tail = head n = 1

while tail.next: tail = tail.next n += 1

k %= n

if k == 0: return head

tail.next = head

steps_to_new_tail = n - k new_tail = tail

for _ in range(steps_to_new_tail): new_tail = new_tail.next

new_head = new_tail.next new_tail.next = None

return new_head

Complexity: Time: O(n) Space: O(1)

The key mental model is: rotation + cycle manipulation

Whenever you see:

“Rotate a linked list”

think: k %= n tail → head cut at correct position

20. Even-Odd Merge

An important clarification: This does not mean even-valued and odd-valued nodes. It means even and odd positions. Given: L0 → L1 → L2 → L3 → L4

produce: L0 → L2 → L4 → L1 → L3

The clean approach is to maintain two chains: even odd

Traverse the original list: L0 → even L1 → odd L2 → even L3 → odd …

Then connect: even_tail.next = odd_head

Python: def even_odd_merge(head): if not head: return None

even_dummy = ListNode() odd_dummy = ListNode()

even_tail = even_dummy odd_tail = odd_dummy

is_even = True

while head: next_node = head.next

if is_even: even_tail.next = head even_tail = even_tail.next else: odd_tail.next = head odd_tail = odd_tail.next

head = next_node is_even = not is_even

odd_tail.next = None even_tail.next = odd_dummy.next

return even_dummy.next

Complexity: Time: O(n) Space: O(1)

The existing nodes are reused.

21. Linked-List Palindrome

This problem connects directly to Part 6’s string palindrome. For strings: left → ← right

Random access makes the problem easy. For linked lists: head → → → middle → → tail

there is no backward pointer. So we need a different algorithm. The solution: Find middle ↓ Reverse second half ↓ Compare

For: 1 → 2 → 3 → 2 → 1

split into: 1 → 2 → 3 2 → 1

Reverse the second half: 1 → 2

Then compare: 1 == 1 2 == 2

Python: def is_palindrome(head): if not head or not head.next: return True

slow = fast = head

while fast and fast.next: slow = slow.next fast = fast.next.next

second_half = reverse_list(slow)

first = head second = second_half

while second: if first.data != second.data: return False

first = first.next second = second.next

return True

Reverse helper: def reverse_list(head): prev = None current = head

while current: nxt = current.next current.next = prev prev = current current = nxt

return prev

Complexity: Time: O(n) Space: O(1)

If the original list must remain unchanged, reverse the second half again after comparison to restore it.

22. List Pivoting: Three-Way Partition

Given: 3 → 2 → 2 → 11 → 7 → 5 → 11

with pivot: k = 7

produce: 3 → 2 → 2 → 5 → 7 → 11 → 11

But there’s an important requirement:

Preserve the relative order within each group.

Create three chains: less equal greater

For each node: if node.data < k: less elif node.data == k: equal else: greater

Finally: less → equal → greater

This is essentially the linked-list version of three-way quicksort partitioning. Python: def list_pivoting(head, k): less_dummy = ListNode() equal_dummy = ListNode() greater_dummy = ListNode()

less = less_dummy equal = equal_dummy greater = greater_dummy

while head: next_node = head.next

if head.data < k: less.next = head less = less.next

elif head.data == k: equal.next = head equal = equal.next

else: greater.next = head greater = greater.next

head = next_node

greater.next = None equal.next = greater_dummy.next less.next = equal_dummy.next

return less_dummy.next

Complexity: Time: O(n) Space: O(1)

The broader pattern is: < pivot = pivot > pivot

This connects linked lists with:

Dutch National Flag
quicksort partitioning
stable partitioning
linked-list transformations

23. Add Two List-Based Integers

This is an especially interesting problem because it introduces arbitrary-precision arithmetic. Suppose: L1: 3 → 1 → 4

represents: 413

because the least significant digit comes first. And: L2: 7 → 0 → 9

represents: 907

Their sum: 1320

is represented as: 0 → 2 → 3 → 1

Why not convert them to Python integers? Because the lists can be arbitrarily long. Instead, simulate grade-school addition.

Grade-School Addition

413

1320

Process from the least significant digit: 3 + 7 = 10 → write 0 → carry 1

1 + 0 + 1 = 2

4 + 9 = 13 → write 3 → carry 1

remaining carry = 1

Python: def add_two_numbers(L1, L2): dummy = ListNode() tail = dummy carry = 0

while L1 or L2 or carry: value = carry

if L1: value += L1.data L1 = L1.next

if L2: value += L2.data L2 = L2.next

tail.next = ListNode(value % 10) tail = tail.next

carry = value // 10

return dummy.next

Complexity: Time: O(n + m) Space: O(max(n, m))

The deeper pattern is: digit + carry

which also appears in:

addition
multiplication
arbitrary-precision arithmetic
big-integer libraries

24. The 10 Most Important Linked-List Patterns

Now let’s compress the entire Part.

Pattern 1 — Dummy Head

Use when the head may change. dummy = ListNode(0, head)

Useful for:

merge
delete
kth-last
partition
even/odd merge

Pattern 2 — Fast + Slow Pointers

Use when you need:

middle
cycle
relative positioning

Core: slow = slow.next fast = fast.next.next

Pattern 3 — Fixed Gap

For kth-last problems: first –––––––– k –––––––– second

Advance the first pointer by k, then move both together.

Pattern 4 — Reverse Links

Core template: prev = None current = head

while current: nxt = current.next current.next = prev prev = current current = nxt

The invariant:

prev is the head of the reversed processed portion, while current is the first unprocessed node.

This invariant is more important than memorizing the code.

25. Pattern 5 — Merge Chains

When combining linked lists: p1 p2 tail

Use a dummy node and attach one node at a time.

26. Pattern 6 — Split Into Multiple Chains

Useful for: even / odd

or: less / equal / greater

Then concatenate the chains. This technique is powerful because it lets you preserve relative ordering while avoiding expensive rearrangements.

27. Pattern 7 — Length Alignment

If two lists eventually converge: compute lengths ↓ align remaining lengths ↓ walk together

This pattern also generalizes to:

tree paths
streams
synchronized iterators

28. Pattern 8 — Cycle Analysis

For cycle-related problems: Does a cycle exist? ↓ Where does it start? ↓ Do two cycles overlap?

Don’t attempt to solve all cases simultaneously. Break the problem into stages. This is a general algorithm-design principle:

Decompose a complicated structural problem into simpler decisions.

29. Pattern 9 — Exploit Sortedness

If the input is sorted: duplicates are adjacent

Therefore: O(n) scan

can replace: O(n) hash space

Always ask:

What structural property can I exploit?

30. Pattern 10 — Treat the List as a Number

For arithmetic: digit + carry

This naturally leads to: value = a + b + carry digit = value % 10 carry = value // 10

This pattern extends beyond linked lists into arbitrary-precision arithmetic.

31. Complexity Cheat Sheet

Problem	Time	Extra Space
Merge sorted lists	O(n + m)	O(1)
Reverse sublist	O(n) / O(f)	O(1)
Detect cycle	O(n)	O(1)
Overlap, no cycle	O(n + m)	O(1)
Overlap, possible cycles	O(n + m)	O(1)
Delete given node	O(1)	O(1)
Remove kth-last	O(n)	O(1)
Remove duplicates	O(n)	O(1)
Right shift	O(n)	O(1)
Even-odd merge	O(n)	O(1)
Linked-list palindrome	O(n)	O(1)
Pivot list	O(n)	O(1)
Add list integers	O(n + m)	O(max(n, m))

These align with the complexity of the corresponding solutions in the source material.

32. The Six Problems I Would Prioritize

For Staff/Principal-level coding interviews, I’d prioritize these first.

#1 — Merge Two Sorted Lists

Master: dummy tail p1 p2

#2 — Reverse a Sublist

Master: pointer rewiring

#3 — Cycle Detection

Be able to explain: Floyd’s algorithm why pointers meet how to find cycle start

#4 — Overlapping Lists

Master: tail identity length alignment cycle + overlap case analysis

#5 — kth-Last Element

Immediately recognize: fixed-gap two pointers

#6 — List Pivoting

Understand: less / equal / greater

and how it connects linked lists to partitioning and quicksort.

33. What to Memorize vs What to Understand

Don’t memorize entire implementations. Memorize these conceptual templates.

Reverse

prev = None cur = head

while cur: nxt = cur.next cur.next = prev prev = cur cur = nxt

Fast / Slow

slow = head fast = head

while fast and fast.next: slow = slow.next fast = fast.next.next

Dummy

dummy = ListNode(0, head)

Merge

tail.next = chosen tail = tail.next

Fixed Gap

for _ in range(k): first = first.next

while first: first = first.next second = second.next

Partition

less → equal → greater

Addition

value = a + b + carry digit = value % 10 carry = value // 10

These templates should become mental reflexes.

34. What NOT to Memorize

Don’t memorize the complicated implementation for overlapping cyclic lists. Instead, remember the decision tree: Detect cycles │ ┌──────────┼──────────┐ │ │ │ neither one only both │ │ │ ▼ ▼ ▼ 7.4 no overlap compare cycles │ ┌──────┴──────┐ ▼ ▼ same cycle different │ │ align stems no overlap

The decision structure is more valuable than memorizing dozens of pointer operations.

35. Part 6 → Part 7: Same Patterns, Different Data Structure

This connection is extremely important. Part 6 dealt with strings: strings ↓ two pointers ↓ reverse ↓ run scanning

Part 7 takes the same ideas into a structure where you cannot jump backward. Consider a palindrome.

Part 6 — String

left → ← right

Easy because strings support indexing.

Part 7 — Linked List

head → → → middle → → tail

There is no backward pointer. Therefore we need: find middle ↓ reverse second half ↓ compare

This is a powerful general lesson:

The data structure can change the algorithm even when the underlying problem is identical.

36. The Most Important Concept: Node Identity

For linked lists, don’t think primarily about values. Think about:

NODE REFERENCES

For example: a.data == b.data

doesn’t mean: a is b

Two different nodes can contain the same value. Identity matters in:

cycle detection
overlapping lists
merging
deletion
graph-like structures

This is one of the most important conceptual differences between linked-list problems and many array problems.

37. A Linked-List Debugging Checklist

When your code fails, check these systematically.

1. Did I lose the next node?

Bad: cur.next = prev cur = cur.next

You just lost the original next node. Correct: nxt = cur.next cur.next = prev cur = nxt

2. Did I accidentally create a cycle?

After pointer rewiring, verify that the final tail points to: None

when the list is supposed to be acyclic.

3. Did I forget the head case?

Always test: empty list single node two nodes

4. Did I confuse node equality with value equality?

Use: a is b

when checking node identity.

5. Did I update the correct predecessor?

This is especially important for:

deletion
reversal
partitioning

38. Edge Cases You Should Always Test

For almost every Part 7 problem, test: [] [1] [1, 2]

Then: head changes tail changes all values equal duplicate values k = 1 k = n

For cycle problems: no cycle cycle starts at head cycle starts in middle self-loop

For overlap: no overlap overlap at tail overlap at head one list completely contained in another

Systematic edge-case testing is particularly important at Staff level because pointer bugs often hide in boundary conditions.

39. The Staff-Level Interview Perspective

At Staff level, don’t just say:

“I’ll use two pointers.”

Explain why. Suppose the interviewer asks:

“Merge two sorted linked lists.”

A weak answer:

“I’ll use two pointers.”

A stronger answer:

“Because both lists are sorted, I can maintain an invariant that the merged prefix is already sorted. At each step I append the smaller current node. I reuse the existing nodes, so the algorithm takes O(n + m) time and O(1) auxiliary space. A dummy head removes the special case around constructing the first node.”

That demonstrates: Algorithm + Invariant + Complexity + Memory + Implementation robustness

That’s the level of reasoning expected from a Staff engineer.

40. Invariants You Should Be Able to State

This is one of the most important upgrades you can make in your interview preparation.

Merge

tail points to the last node of the sorted merged prefix.

Reverse

prev is the reversed processed portion, while current is the unprocessed portion.

Cycle Detection

Fast advances twice as quickly as slow; if a cycle exists, their relative distance eventually becomes zero modulo the cycle length.

kth-Last

The distance between first and second remains exactly k nodes.

Partition

Every node already placed in less, equal, or greater satisfies its predicate and preserves relative ordering.

Palindrome

The first half and reversed second half are compared node-for-node.

Being able to state these invariants clearly is a major step toward Staff-level coding performance.

41. The Part 7 Pattern Map

LINKED LIST │ ┌───────────────────┼───────────────────┐ ▼ ▼ ▼ MERGE REVERSE DETECT │ │ │ 7.1 7.2 7.3 │ ▼ OVERLAP │ ┌───┴────┐ ▼ ▼ 7.4 7.5 │ ├───────────────┐ ▼ ▼ DELETE TWO POINTER │ │ 7.6 ┌─────┴─────┐ ▼ ▼ 7.7 7.11 │ │ kth-last palindrome

┌──────────────────────────┐ ▼ ▼ PARTITION REORDER │ │ 7.12 ┌─────┴─────┐ ▼ ▼ 7.9 7.10 rotate even/odd

┌──────────────────────────────┐ ▼ ▼ DATA PROCESSING ARITHMETIC │ │ 7.8 7.13 duplicates addition

The apparent variety of the problems hides a relatively small set of reusable techniques.

42. Final Interview Cheat Sheet

When you see:

“Merge two sorted linked lists”

Think: two pointers + dummy + tail

“Reverse linked list/sublist”

Think: prev / current / next

“Cycle”

Think: slow / fast

“Find cycle beginning”

Think: cycle length + aligned pointers

“Two lists overlap”

Think: same tail + length alignment

“kth from end”

Think: fixed gap

“Delete node when only node pointer is given”

Think: copy successor

“Sorted list duplicates”

Think: skip equal consecutive nodes

“Rotate linked list”

Think: k %= n tail → head cut at n-k

“Even/odd positions”

Think: two chains

“Palindrome”

Think: middle + reverse second half + compare

“Pivot around k”

Think: less / equal / greater

“Huge integers represented as lists”

Think: digit + carry

43. The Five Concepts I Would Make Automatic

For Staff/Principal coding interviews, make these five almost reflexive:

1. Dummy Node

↓ Simplifies head manipulation

2. Fast + Slow Pointers

↓ Middle / cycle / relative distance

3. Pointer Reversal

↓ prev / current / next

4. Length Alignment / Fixed Gap

↓ Overlap / kth-last

5. Multiple Chains

↓ Merge / partition / even-odd

If these five become automatic, most of Part 7 becomes a variation of something you already understand.

Final Takeaway

Part 7 is fundamentally about manipulating references safely. The progression is deliberate: Merge ↓ Reverse ↓ Cycle ↓ Overlap ↓ Overlap + Cycles ↓ O(1) Deletion ↓ Fixed-Gap Pointers ↓ Exploit Sortedness ↓ Rotation ↓ Multiple Chains ↓ Reverse + Compare ↓ Three-Way Partition ↓ Arbitrary-Precision Addition

But underneath these 13 problems are just a few core ideas: Dummy nodes + Pointer rewiring + Fast / slow pointers + Fixed-gap pointers + Length alignment + Multiple linked chains

That is the real knowledge you should carry into an interview. Don’t memorize 13 solutions. Learn to recognize the transformation. When you see a linked-list problem, ask:

What references need to move?

Then ask:

What invariant must remain true while I move them?

Finally:

Can I solve it without allocating unnecessary memory?

That mindset turns linked lists from a collection of tricky pointer puzzles into a small, reusable set of patterns. And that is exactly the skill that matters at Staff level.

Up Next: Part 8 — Stacks & Queues

Part 7 taught us to reason about: nodes + references + pointer movement + structural invariants

Part 8 shifts the focus toward controlled access patterns: Stack ↓ LIFO ↓ Queues ↓ FIFO ↓ Monotonic structures ↓ Expression processing ↓ Scheduling and buffering

The data structure changes. But the core interview skill remains the same:

Recognize the pattern, maintain the invariant, and choose the simplest representation that makes the algorithm correct.