Topic 6: Linked List

Canonical Questions #

Pointer Reversal & Reordering #

Reverse entire linked list or segments
Swap nodes or reorder structure

Problems #

for the recursive one, do the checks correctly and let the wishful thinking take care of it. For the iterative one, use a prev node to keep track of one-history and carry on with a while loop – this is something like using a lookahead pointer.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
   class Solution:
     def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
       prev, curr = None, head
         while curr:
           right = curr.next # node to the right of this, tmp pointer
           curr.next = prev  # reset curr to point to prev
           prev = curr       # prev can be updated to curr, ready for next iteration
           curr = right      # curr is now right (tmp pointer), ready for next iteration

         return prev

Code Snippet 1: Reverse Linked List (206) – iterative solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
   class Solution:
     def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
         if not head or not head.next:
             return head

         tmp = head
         next_node = tmp.next
         new_head = self.reverseList(tmp.next)
         next_node.next = tmp
         tmp.next = None

         return new_head

Code Snippet 2: Reverse Linked List (206) – recursive solution

Pattern Extraction

Core Insight: At each step, redirect the current node’s next pointer to the previous node. Three pointers (prev, curr, next_temp) march through the list, reversing one link per step. Pattern Name: In-Place Pointer Reversal Canonical Section: Linked List > Reversal Recognition Signals:

“Reverse a linked list” (full or partial)
In-place modification required ($O(1)$ space)
The reversal is a building block for many other linked list problems

Anti-Signals:

Need to reverse the VALUES, not the links – just swap values using an array
Doubly-linked list – reversal is simpler (swap prev and next for each node)

Decision Point: Full reversal = single pass with three pointers. Partial reversal (range $[m, n]$) = connect pre-start to reversed segment. This is THE fundamental linked list operation.

Pitfalls and Misconceptions

Trap: Losing the reference to the next node before redirecting the current node’s next pointer. Why: After curr.next = prev, the link to the rest of the list is lost. Correction: Save next_temp = curr.next BEFORE modifying curr.next.
Trap: Not returning prev (the new head) after the loop. Why: After the loop, curr is None and prev points to the last processed node (new head). Correction: Return prev as the new head of the reversed list.

Problem Mutations

What if you needed to reverse only nodes $m$ to $n$? (stress-tests: full reversal assumption) Navigate to position $m-1$, reverse the segment, reconnect. Connects to LC 92 Reverse Linked List II.
What if you needed to reverse in groups of $k$? (stress-tests: single reversal) Recursively/iteratively reverse each group of $k$ nodes, connecting segments. Connects to LC 25 Reverse Nodes in k-Group.
What if you needed to check if the list is a palindrome? (stress-tests: reversal purpose) Find middle (fast/slow), reverse second half, compare. Connects to LC 234 Palindrome Linked List.

AI usage disclosure Claude Opus 4.6 · content enrichment

Standardised annotation dropdowns for Reverse Linked List generated via batch canonical enrichment pass. Review against personal solving experience and adjust.

Reverse Linked List II (92)

This applies only to a partial segment of the list. Nothing that special here, just use the dummy node to make life easier.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
   # Definition for singly-linked list.
   # class ListNode:
   #     def __init__(self, val=0, next=None):
   #         self.val = val
   #         self.next = next
   class Solution:
     def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
       """
         This is a single pass solution.
         """

         # trivial edge case:
         if left == right:
             return head

         dummy = ListNode(0, head)
         prev = dummy

         # move prev to left of Left Node
         for _ in range(left - 1):
           prev = prev.next

         # curr becomes the first node to be reversed:
         curr = prev.next

         # now we reverse for (right - left) times
         for _ in range(right - left):
           tmp = curr.next
           curr.next = tmp.next
           tmp.next = prev.next
           prev.next = tmp

         return dummy.next

Code Snippet 3: Reverse Linked List II (92)

Pattern Extraction

Core Insight: Navigate to position $m-1$ (the node before the reversal start), reverse the segment $[m, n]$ using standard three-pointer reversal, then reconnect: the pre-start node points to the new head of the reversed segment, and the original head of the reversed segment points to the node after the reversal end. Pattern Name: Partial In-Place Linked List Reversal Canonical Section: Linked List > Reversal Recognition Signals:

“Reverse a linked list from position $m$ to $n$”
In-place modification, single pass required
Dummy head simplifies edge cases (reversing from position 1)

Anti-Signals:

Full list reversal – simpler, no reconnection needed. That’s LC 206
Reverse in groups of $k$ – recursive/iterative group processing. Connects to LC 25

Decision Point: Partial reversal = navigate to start, reverse segment, reconnect. Full reversal = simpler three-pointer sweep. Group reversal = iterated partial reversals.

Pitfalls and Misconceptions

Trap: Not using a dummy head, failing when $m = 1$ (reversing from the head). Why: When the head itself is part of the reversed segment, you need a node before it to reconnect. Correction: dummy = ListNode(0, head). Start navigation from dummy.
Trap: Losing track of the reconnection points after reversal. Why: After reversing $[m, n]$, the node that was originally at position $m$ is now the tail of the reversed segment. It needs to point to node $n+1$. Correction: Before reversing, save con = pre (node before segment) and tail = curr (node at position $m$, which becomes the tail). After reversing: con.next = prev (new head), tail.next = curr (node after segment).

Problem Mutations

What if you needed to reverse every other segment? (stress-tests: single segment) Navigate and reverse alternating segments. More pointer bookkeeping but same core reversal logic.
What if you needed to reverse in groups of $k$? (stress-tests: arbitrary range) Iterated partial reversals: reverse $k$ nodes, reconnect, advance, repeat. Connects to LC 25 Reverse Nodes in k-Group.
What if the list were doubly-linked? (stress-tests: singly-linked) Reversal is simpler: swap prev and next for each node in the segment. But reconnection logic is the same.

AI usage disclosure Claude Opus 4.6 · content enrichment

Standardised annotation dropdowns for Reverse Linked List II generated via batch canonical enrichment pass. Review against personal solving experience.

Reverse Nodes in k-Group (25)

The recursive version is the most intuitive for me, just do it for the first k then call the same function again on the sublist.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
   class Solution:
      def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
         # Check if there are at least k nodes left
          node = head
          for _ in range(k):
              if not node:
                  return head
               node = node.next

          # Reverse k nodes
          prev, curr = None, head
          for _ in range(k):
             nxt = curr.next
             curr.next = prev
             prev = curr
             curr = nxt

          # Recursively process the rest
          head.next = self.reverseKGroup(curr, k)
          return prev

Code Snippet 4: Reverse Nodes in k-Group (25)

Here’s an iterative version, we rely on a reverse helper function for the local segments and let the original function drive it.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
   # Definition for singly-linked list.
   # class ListNode:
   #     def __init__(self, val=0, next=None):
   #         self.val = val
   #         self.next = next
   class Solution:
      # Reverse nodes from left.next up to (but not including) nxt.
      # After reversal, left.next points to the new head of the reversed group,
      # and the original group head becomes the new 'left' for the next group.
      def reverse(self, left, right, nxt):
         prev, curr = None, left.next
         group_head = curr  # Will become the tail after reversal

          while curr != nxt:
             tmp = curr.next
             curr.next = prev
             prev = curr
             curr = tmp

          # Connect the reversed group with the previous part and the next group
          left.next = prev
          group_head.next = nxt

          # Return the tail of the reversed group (which is group_head)
          return group_head

      def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
         dummy = ListNode(0, head)
         left = dummy

          while True:
             # Lookahead check if there are k nodes ahead
              right = left
              for _ in range(k):
                 right = right.next
                  if not right:
                      return dummy.next  # Not enough nodes left for another group

              nxt = right.next  # Node after the k-group
              # Reverse the k nodes between left and right (inclusive)
              left = self.reverse(left, right, nxt)  # left now points to the tail of the reversed group

          # return dummy.next  # (Unreachable, but kept for clarity)

Code Snippet 5: Reverse Nodes in k-Group (25)

Pattern Extraction

Core Insight: Iteratively reverse each group of $k$ nodes, then reconnect segments. Check if $k$ nodes remain before reversing (don’t reverse partial groups). Use a dummy head for clean reconnection. Pattern Name: Iterated Partial Reversal with Group Counting Canonical Section: Linked List > Reversal Recognition Signals:

“Reverse every $k$ nodes” in a linked list
Don’t reverse the last group if fewer than $k$ nodes
In-place modification

Anti-Signals:

Reverse a specific range $[m, n]$ – single partial reversal (LC 92)
Reverse pairs (k=2) – simpler special case (LC 24)

Decision Point: Group reversal = count $k$ nodes, reverse, reconnect, advance. The counting step is what distinguishes this from LC 92.

Pitfalls and Misconceptions

Trap: Not checking if $k$ nodes remain before reversing. Why: The last group may have fewer than $k$ nodes and should NOT be reversed. Correction: Count forward $k$ nodes from the current position. If fewer than $k$ remain, leave them as-is.
Trap: Losing track of the connection points between reversed groups. Why: After reversing a group, you need to connect: previous group’s tail -> new head; old head (now tail) -> next group. Correction: Save group_prev (the node before the group) and group_tail (first node of the group, which becomes the tail after reversal).

Problem Mutations

What if you should reverse ALL groups including the last partial one? (stress-tests: skip partial) Remove the count check. Always reverse whatever remains.
What if $k$ changed per group? (stress-tests: fixed $k$) Need a sequence of $k$ values. Process each group with its own $k$.

AI usage disclosure Claude Opus 4.6 · content enrichment

Batch annotation for Reverse Nodes in k-Group.

Swap Nodes in Pairs (24)

Classic swapping logic, using a dummy helps a lot. The rest of it is just careful pointer management.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
   # Definition for singly-linked list.
   # class ListNode:
   #     def __init__(self, val=0, next=None):
   #         self.val = val
   #         self.next = next
   class Solution:
      def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
          if (not head) or (head and not head.next):
              return head

          dummy = ListNode()
          prev = dummy
          ptr = head
          while (first:=ptr) and (second:=ptr.next):
             next_join = second.next
             second.next = first
             first.next = next_join
             prev.next = second
             prev = first
             ptr = next_join

          return dummy.next

Code Snippet 6: Swap Nodes in Pairs (24)

Pattern Extraction

Core Insight: Special case of reverse-k-group with $k = 2$. For each pair, swap the two nodes by redirecting pointers. Pattern Name: Pairwise Node Swapping Canonical Section: Linked List > Reversal Recognition Signals:

“Swap every two adjacent nodes”
Special case of k-group reversal with k=2

Anti-Signals:

General k-group reversal – LC 25

Decision Point: k=2 simplifies the reversal to a single pointer swap per pair. Use a dummy head.

Pitfalls and Misconceptions

Trap: Swapping values instead of nodes. Why: The problem says “swap nodes,” not “swap values.” Node structure must change. Correction: Redirect next pointers to actually move nodes in the list.

Problem Mutations

What if $k > 2$? (stress-tests: pair swap) Generalises to LC 25.

AI usage disclosure Claude Opus 4.6 · content enrichment

Batch annotation for Swap Nodes in Pairs.

Reorder List (143)

We need to end up zipping first half with the reverse of the second half. We first find the midpoint by using fast and slow pointers then we split it into two lists and reverse the second list. Finally we treat it as a zip operation and get our answer. Key trick: By splitting and reversing, you can walk from both ends simultaneously without extra storage.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
   class Solution:
      def reorderList(self, head: Optional[ListNode]) -> None:
         # early exits for the trivial edge cases:
          if not head or not head.next:
              return

          # Step 1: Find the middle, it's where the slow pointer is at when the fast pointer has reached the end.
          slow, fast = head, head
          while fast and fast.next:
             slow = slow.next
             fast = fast.next.next

          # Step 2: Reverse the second half, slow is now at the middle
          prev, curr = None, slow.next
          slow.next = None  # Split the list, now we have 2 lists
          while curr:
             next_temp = curr.next
             curr.next = prev
             prev = curr
             curr = next_temp

          # Step 3: Merge two halves, this is like a ZIP operation
          first, second = head, prev
          while second:
             tmp1, tmp2 = first.next, second.next
             first.next = second
             second.next = tmp1
             first, second = tmp1, tmp2

Code Snippet 7: Reorder List (143)

Pattern Extraction

Core Insight: Three steps: (1) find the middle using fast/slow pointers, (2) reverse the second half, (3) merge the two halves by alternating nodes. Pattern Name: Split-Reverse-Merge Canonical Section: Linked List > Multi-Step Manipulation Recognition Signals:

“Reorder to $L_0 → L_n → L_1 → L_n-1 → …$”
Interleaving from both ends
In-place with $O(1)$ space

Anti-Signals:

Can use $O(n)$ space – extract to array, reindex, rebuild

Decision Point: The three-step approach is the canonical in-place solution. Each step is a well-known linked list primitive.

Pitfalls and Misconceptions

Trap: Using an array to store all nodes and then rebuilding ($O(n)$ space). Why: Works but violates the $O(1)$ space constraint. Correction: Split (fast/slow), reverse second half, merge.
Trap: Not properly terminating the first half after splitting. Why: The first half’s last node still points to the (now-reversed) second half. This creates a cycle. Correction: After finding the middle, set slow.next = None to terminate the first half.

Problem Mutations

What if the list were doubly-linked? (stress-tests: singly-linked) Simpler: use head and tail pointers moving inward, no reversal needed.
What if you needed to reorder in groups of 3 (take from front, back, front)? (stress-tests: pairs) More complex pointer management but same split-reverse-merge approach.

AI usage disclosure Claude Opus 4.6 · content enrichment

Batch annotation for Reorder List.

Merging & Sorting #

Merge two or multiple sorted linked lists
Sort linked list using in-place mergesort

Problems #

Merge Two Sorted Lists (21)

Init a dummy node then consume from two providers (the two sorted lists), each time shifting the pointer when you consume. Eventually we can just graft the longer linked list over.

The key mental model here is to think of the others as providers.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
   # Definition for singly-linked list.
   # class ListNode:
   #     def __init__(self, val=0, next=None):
   #         self.val = val
   #         self.next = next
    class Solution:
        def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
            dummy = ListNode()
            current = dummy

            # build up from current by using candidates from provider lists, list1 and list2
            while list1 and list2:
                if list1.val < list2.val:
                    current.next = list1
                    list1 = list1.next
                else:
                    current.next = list2
                    list2 = list2.next

                # advance the builder pointer
                current = current.next

            # Remnants: Attach the remaining part
            current.next = list1 if list1 else list2

            return dummy.next

Code Snippet 8: Merge Two Sorted Lists (21)

Pattern Extraction

Core Insight: Compare the heads of both lists, pick the smaller, advance that list’s pointer. A dummy head simplifies edge cases. Pattern Name: Two-Pointer Merge (Linked List) Canonical Section: Linked List > Merge Operations Recognition Signals:

Two sorted linked lists to merge into one sorted list
Maintain sorted order
In-place (reuse existing nodes)

Anti-Signals:

More than two lists – use a heap or divide-and-conquer. Connects to LC 23
Lists are unsorted – sort first, then merge

Decision Point: Two lists = simple iterative merge. K lists = heap ($O(n \log k)$) or divide-and-conquer ($O(n \log k)$).

Pitfalls and Misconceptions

Trap: Not using a dummy head, leading to complex edge cases for the first element. Why: Without a dummy, you need to separately determine which list provides the head. Correction: dummy = ListNode(0); tail = dummy. Return dummy.next at the end.
Trap: Not handling the remaining elements when one list is exhausted. Why: After the merge loop, one list may still have elements. These must be appended. Correction: After the loop: tail.next = l1 if l1 else l2.

Problem Mutations

What if there were $k$ sorted lists? (stress-tests: two lists) Use a min-heap of size $k$ to always pick the smallest current head. $O(n \log k)$ total. Connects to LC 23 Merge K Sorted Lists.
What if the lists were doubly-linked? (stress-tests: singly-linked) Same merge logic, but also set prev pointers. More bookkeeping, same complexity.
What if you needed to merge sorted arrays instead of lists? (stress-tests: data structure) Same two-pointer merge. This is the merge step of merge sort.

AI usage disclosure Claude Opus 4.6 · content enrichment

Standardised annotation dropdowns for Merge Two Sorted Lists generated via batch canonical enrichment pass. Review against personal solving experience.

Merge K Sorted Lists (23)

Same concept as 2 sorted lists, just maintain k providers. We have two solutions, one that is space-optimal $O(N / logk)$ time $O(1)$ space and one that is not $O(N / logk)$ time $O(k)$ space .

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
    class Solution:
        def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
            if not lists:
                return None
            n = len(lists)
            interval = 1
            while interval < n:
                for i in range(0, n - interval, interval * 2):
                    lists[i] = self.merge2Lists(lists[i], lists[i + interval])
                    interval *= 2
            return lists[0] if n > 0 else None

        def merge2Lists(self, l1, l2):
            dummy = curr = ListNode()
            while l1 and l2:
                if l1.val < l2.val:
                    curr.next, l1 = l1, l1.next
                else:
                    curr.next, l2 = l2, l2.next
                    # advance
                curr = curr.next

            curr.next = l1 or l2

            return dummy.next

Code Snippet 9: Merge K Sorted Lists (23)

The easiest way imo to get the best value each time is to just use a priority queue. I prefer the PQ solution.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
   import heapq

    # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, val=0, next=None):
    #         self.val = val
    #         self.next = next
    class Solution:
        def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
            # filters away the empty lists:
            # NOTE: the use of id(ls) is to give a tie-breaker in the case that two lists have the same value.
            #       this id usage is an easy way to avoid compiler issues
            providers = [(ls.val, id(ls), ls)
                         for ls in lists
                         if ls]
            heapq.heapify(providers)
            pre_head = dummy = ListNode()

            while providers:
                (val, _, ls) = heapq.heappop(providers)
                dummy.next = ls
                if ls.next:
                    ls = ls.next
                    new_val = ls.val
                    heapq.heappush(providers, (new_val, id(ls), ls))

                dummy = dummy.next

            return pre_head.next

Code Snippet 10: Merge K Sorted Lists (23) – PQ approach

Pattern Extraction

Core Insight: A min-heap of size $k$ always holds the current smallest element from each list. Pop the smallest, advance that list’s pointer, push the new head. Alternatively, divide-and-conquer: merge pairs of lists recursively. Pattern Name: K-Way Merge with Min-Heap Canonical Section: Linked List > Merge Operations / Heap > K-Way Merge Recognition Signals:

$k$ sorted sequences to merge into one
$O(n \log k)$ time ($n$ = total elements)
Min-heap of size $k$ for efficient selection

Anti-Signals:

Only two lists – simple iterative merge, no heap needed
Lists are unsorted – sort each first, then merge
Need to merge in a specific interleaving pattern – not a simple merge

Decision Point: Heap approach: $O(n \log k)$, straightforward. Divide-and-conquer: also $O(n \log k)$, recursive. Both are optimal. Heap is more general (works for any $k$ sorted streams); D&C is specific to lists.

Pitfalls and Misconceptions

Trap: Merging lists one by one (sequentially): merge list 1 with 2, result with 3, etc. Why: This is $O(kn)$ because each merge pass touches all accumulated elements. With $k$ passes, total work is $O(kn)$. Correction: Use a heap ($O(n \log k)$) or divide-and-conquer ($O(n \log k)$) for balanced merging.
Trap: Pushing None nodes into the heap. Why: Empty lists produce None heads. Pushing None into the heap causes comparison errors. Correction: Filter out None before pushing: heap = [(node.val, i, node) for i, node in enumerate(lists) if node].
Trap: Comparing ListNode objects directly in the heap (Python can’t compare custom objects). Why: If two nodes have equal values, Python tries to compare the nodes themselves, which fails. Correction: Include a unique tiebreaker in the heap tuple: (node.val, list_index, node).

Problem Mutations

What if the inputs were sorted arrays instead of lists? (stress-tests: data structure) Same heap approach with index pointers instead of node pointers. This is the external merge sort pattern.
What if elements arrived as streams (online)? (stress-tests: static lists) Heap-based merge is inherently online. Push new elements as they arrive from each stream.
What if you needed to merge K sorted arrays into one sorted array in $O(n)$ space? (stress-tests: space) Heap-based merge uses $O(k)$ space for the heap plus $O(n)$ for output. In-place merge is much harder ($O(n \log k)$ time, $O(1)$ space is possible with complex algorithms).

AI usage disclosure Claude Opus 4.6 · content enrichment

Standardised annotation dropdowns for Merge K Sorted Lists generated via batch canonical enrichment pass. Review against personal solving experience.

TODO Sort List (148)

Cycle & Intersection Detection #

some basic capabilities:
- Detect cycle presence and start
- Detect intersection of two lists
Use Floyd’s Tortoise and Hare or two-pointer tricks. This can be used to find the actual source of the cycle / duplicate as well.

Problems #

Linked List Cycle (141) Classic tortoise and hare, just check if they meet (have cycle) or we reach the end of the list.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
    class Solution:
        def hasCycle(self, head: Optional[ListNode]) -> bool:
            slow, fast = head, head
            while fast and fast.next:
                # if fast and fast.next are valid, they would have checked the previous nodes so slow will always be valid
                slow = slow.next
                fast = fast.next.next
                if slow == fast:
                    return True
            return False

Code Snippet 11: Linked List Cycle (141)

Pattern Extraction

Core Insight: Floyd’s tortoise and hare: slow pointer moves 1 step, fast moves 2. If they meet, there’s a cycle. If fast reaches null, no cycle. Pattern Name: Floyd’s Cycle Detection (Tortoise and Hare) Canonical Section: Linked List > Cycle Detection Recognition Signals:

“Does the linked list have a cycle?”
$O(1)$ space required (no hash set)
Two pointers moving at different speeds

Anti-Signals:

Need the cycle START node, not just existence – after detection, reset one pointer to head and advance both at speed 1 until they meet. Connects to LC 142
Can use $O(n)$ space – hash set of visited nodes is simpler

Decision Point: $O(1)$ space = Floyd’s. $O(n)$ space = hash set. Floyd’s is the canonical approach because it demonstrates the principle.

Pitfalls and Misconceptions

Trap: Not checking fast and fast.next before advancing fast. Why: If fast or fast.next is None, accessing fast.next.next throws a null pointer error. Correction: while fast and fast.next: slow = slow.next; fast = fast.next.next.
Trap: Starting both pointers at different positions. Why: Both must start at head. If they start at different positions, the convergence math breaks. Correction: slow = fast = head. Then advance inside the loop.

Problem Mutations

What if you needed the cycle START, not just existence? (stress-tests: boolean vs position) After detection, reset one pointer to head. Both advance at speed 1. They meet at the cycle start. Connects to LC 142 Linked List Cycle II.
What if the structure weren’t a linked list but an array (next(i) = nums[i])? (stress-tests: linked list structure) Same Floyd’s algorithm but next(i) = nums[i] instead of i.next. Connects to LC 287 Find the Duplicate Number.
What if you needed the cycle length? (stress-tests: existence vs measurement) After detection (pointers meet), keep one stationary and advance the other, counting steps until they meet again. The count is the cycle length.

AI usage disclosure Claude Opus 4.6 · content enrichment

Standardised annotation dropdowns for Linked List Cycle generated via batch canonical enrichment pass. Review against personal solving experience.

Find the Duplicate Number (287)

Treat the array as a linked list (by going to $nums[i]$ as the next pointer because of the question’s premise), use Floyd’s Tortoise and Hare for Cycle Detection then Duplicate Detection: move the fast pointer until they meet. Then to find entrance, move the slow pointer and the other pointer from the start until they meet again.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
    class Solution:
        def findDuplicate(self, nums: List[int]) -> int:
            # Phase 1: Find intersection
            slow = fast = nums[0]
            while True:
                slow = nums[slow]
                fast = nums[nums[fast]] # double jump
                if slow == fast:
                    break

            # Phase 2: Find entrance to the cycle
            fast = nums[0] # reset to beginning
            while slow != fast:
                slow = nums[slow]
                fast = nums[fast]
            return slow

Code Snippet 12: Find the Duplicate Number (287)

Technically there’s the binary search method that exploits the Pigeonhole Principle, but this is inferior because it’s slow:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
    class Solution:
        def findDuplicate(self, nums: List[int]) -> int:
            left, right = 1, len(nums) - 1
            while left < right:
                mid = (left + right) // 2
                count = sum(num <= mid for num in nums)
                if count > mid:
                    right = mid
                else:
                    left = mid + 1
            return left
    # _Why does the binary search work?_
    # The "pigeonhole principle": more numbers ≤ mid than mid itself means the duplicate is in that range.

Code Snippet 13: Find the Duplicate Number (287)

Intersection of Two Linked Lists (160) The classic two-pointer solution uses the fact that:

If two lists intersect, pointer traversal lengths equalize when each pointer is made to switch lists at the ends, so they meet at intersection or both at None if no intersection.
Explanation:
- Both pointers traverse the lists, switching to the other list after reaching the end, so they travel equal total distances.
- Intersection node reference comparison naturally stops loop.
- The method requires no extra space.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
            class Solution:
                def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
                    if not headA or not headB:
                        return None

                    pointerA, pointerB = headA, headB

                    # Traverse until both pointers meet or both are None
                    while pointerA != pointerB:
                        pointerA = pointerA.next if pointerA else headB
                        pointerB = pointerB.next if pointerB else headA

                    return pointerA  # either intersection or None

Code Snippet 14: Intersection of Two Linked Lists (160)

Pattern Extraction

Core Insight: Two pointers, each traversing both lists. When pointer A reaches the end of list A, redirect to head of list B, and vice versa. They meet at the intersection or both reach null. Pattern Name: Length-Equalising Two-Pointer Traversal Canonical Section: Linked List > Cycle/Intersection Detection Recognition Signals:

“Find the node where two linked lists intersect”
Lists may have different lengths
$O(1)$ space Anti-Signals:
- Lists don’t intersect (both pointers reach null simultaneously)
- Need to find if lists intersect (boolean) – same algorithm, check if meeting point is null
Decision Point: The trick: total distance A + B = B + A. Both pointers traverse the same total distance, arriving at the intersection simultaneously.

Pitfalls and Misconceptions

Trap: Trying to match nodes by value instead of by reference. Why: Different nodes can have the same value. Intersection means same NODE object, not same value. Correction: Compare node references: if ptrA is ptrB:.
Trap: Not handling the non-intersecting case. Why: When lists don’t intersect, both pointers reach None simultaneously. Returning None is correct but must be checked. Correction: The loop terminates when ptrA = ptrB=, which is None for non-intersecting lists.

Problem Mutations

What if you needed the intersection of values (not structural intersection)? (stress-tests: structural) Use hash sets of values. Different problem.
What if the lists had cycles? (stress-tests: no cycles) Need to detect cycles first (Floyd’s), then find intersection of cyclic lists. Much harder.

AI usage disclosure Claude Opus 4.6 · content enrichment

Batch annotation for Intersection of Two Linked Lists.

TODO Linked List Cycle II (142)

Half-Point & Palindromic Checking #

Find middle node using fast/slow pointers
Check if linked list is palindrome (reverse second half and compare)

Problems #

Middle of the Linked List (876)

This is a fast/slow pointer use again. We just let the fast pointer double jump each time. If it can only single jump then the middle is slow.next and if it can’t even single jump then the slow pointer is the middle.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
   # Definition for singly-linked list.
   # class ListNode:
   #     def __init__(self, val=0, next=None):
   #         self.val = val
   #         self.next = next
   class Solution:
       def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
           """
           Fast shall double jump.
           """
           slow, fast = head, head
           while fast:
               if fast.next and fast.next.next:
                   slow = slow.next
                   fast = fast.next.next
               elif fast.next and not fast.next.next:
                   return slow.next
               else:
                   return slow

Code Snippet 15: Middle of the Linked List (876)

Pattern Extraction

Core Insight: Fast/slow pointers. When fast reaches the end, slow is at the middle. Pattern Name: Fast/Slow Pointer (Tortoise and Hare) Canonical Section: Linked List > Fast and Slow Pointers Recognition Signals:

“Find the middle” of a linked list
$O(1)$ space, single pass

Anti-Signals:

Need the exact middle when length is known – just traverse $n/2$ steps

Decision Point: Unknown length + $O(1)$ space = fast/slow. Known length = direct indexing.

Pitfalls and Misconceptions

Trap: Getting the middle definition wrong for even-length lists. Why: “Second middle” (fast and fast.next) vs “first middle” (fast.next and fast.next.next). LC 876 wants the second middle. Correction: while fast and fast.next: slow = slow.next; fast = fast.next.next. When fast is null, slow is the second middle.

Problem Mutations

What if you needed the first middle (for even-length lists)? (stress-tests: second middle) Change the loop condition: while fast.next and fast.next.next. Slow stops one node earlier.
What if this were a doubly-linked list? (stress-tests: singly-linked) Traverse to the end to get length, then traverse $n/2$ steps from head. Or use two pointers from both ends converging inward.

AI usage disclosure Claude Opus 4.6 · content enrichment

Batch annotation for Middle of the Linked List.

TODO Palindrome Linked List (234)

Linked List Arithmetic & Representation #

Add numbers represented as linked lists in forward or reverse order

Problems #

Add Two Numbers (2) Uses a dummy node to build things out and a single loop, always creating new nodes for the result list. The carrying has to be well handled, it’s the one that can have a really long run-on.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
   class Solution:
     def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
       dummy = ListNode()
       tail = dummy
       carry = 0

         p1, p2 = l1, l2
         # single loop that handles the operation, or the carry
         while p1 or p2 or carry:
           val1 = p1.val if p1 else 0
           val2 = p2.val if p2 else 0
           total = val1 + val2 + carry
           carry, digit = divmod(total, 10)
           tail.next = ListNode(digit)
           tail = tail.next

             if p1: p1 = p1.next
             if p2: p2 = p2.next

         return dummy.next

Code Snippet 16: Add Two Numbers (2)

Pattern Extraction

Core Insight: Traverse both lists simultaneously, adding corresponding digits plus carry. Create new nodes for the result. Handle different lengths by treating missing nodes as 0. Pattern Name: Parallel Linked List Traversal with Carry Canonical Section: Linked List > Arithmetic Operations Recognition Signals:

Two linked lists representing numbers (digits in reverse order)
Add digit by digit with carry propagation
Result is a new linked list

Anti-Signals:

Numbers stored in forward order (most significant first) – reverse first or use stack. Connects to LC 445
Multiplication, not addition – different algorithm entirely

Decision Point: Reverse order (least significant first) = direct simulation with carry. Forward order = reverse lists first, then add, then reverse result (or use stacks).

Pitfalls and Misconceptions

Trap: Forgetting to handle the final carry. Why: After both lists are exhausted, there might be a remaining carry (e.g., 99 + 1 = 100). Without appending the carry, the result loses the most significant digit. Correction: After the loop: if carry: current.next = ListNode(carry).
Trap: Assuming both lists are the same length. Why: Lists can have different lengths. Treating a null node as if it has a value causes errors. Correction: Use val1 = l1.val if l1 else 0 and advance only non-null pointers.

Problem Mutations

What if the digits were in forward order? (stress-tests: reverse order) Reverse both lists, add as above, reverse the result. Or use stacks. Connects to LC 445 Add Two Numbers II.
What if you needed to subtract instead of add? (stress-tests: operation type) Determine which number is larger, subtract smaller from larger digit by digit with borrow logic. More edge cases.
What if the result needed to be in-place (modifying one of the input lists)? (stress-tests: new list allocation) Modify the longer list in-place, extending it if a final carry exists. More pointer manipulation.

AI usage disclosure Claude Opus 4.6 · content enrichment

Standardised annotation dropdowns for Add Two Numbers generated via batch canonical enrichment pass. Review against personal solving experience.

TODO Add Two Numbers II (445)

Structural Manipulation & Deletion #

Generally this involves just manipulating the linked list. For objectives such as :
- Deleting nodes by position or value
- Removing duplicates or Nth node from end
- Node insertion and restructuring

Problems #

Remove Nth Node From End of List (19)

This uses an offset pattern, which helps us count nth offset from the end.

We use a dummy node to account for odd cases (such as the head needing to be removed). Then we use 2 pointers to do a single pass, faster pointer has to be n distance away then we advance both so that we can find out which pointer we want to get rid of. Removal is just joining to the adjacent, skipping over that node.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
   # Definition for singly-linked list.
   # class ListNode:
   #     def __init__(self, val=0, next=None):
   #         self.val = val
   #         self.next = next
   class Solution:
      def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
         dummy = ListNode(next=head)
         slow, fast = dummy, dummy

          # move fast for fixed distance for n spots:
          for _ in range(n + 1):
             fast = fast.next

          # move till the end:
          while fast:
             fast = fast.next
             slow = slow.next

          # so the removal target is the node after slow
          # we have to join just adjacent
          slow.next = slow.next.next

          return dummy.next

Code Snippet 17: Remove Nth Node From End of List (19)

Pattern Extraction

Core Insight: Use two pointers separated by $n$ nodes. When the fast pointer reaches the end, the slow pointer is at the node before the target, ready to skip it. Pattern Name: Two-Pointer Gap Technique Canonical Section: Linked List > Deletion Recognition Signals:

“Remove the $n$-th node from the end”
Single pass required
Use a dummy head to handle edge cases (removing the actual head)

Anti-Signals:

Need to remove by value, not position – scan for the value
Need to remove ALL occurrences – full scan needed

Decision Point: “From the end” = two-pointer gap. “From the start” = just traverse $n$ steps.

Pitfalls and Misconceptions

Trap: Not using a dummy head, failing when the head itself needs to be removed. Why: If $n$ equals the list length, the head is the target. Without a dummy, you need a special case. Correction: dummy = ListNode(0, head). Start both pointers from dummy.
Trap: Off-by-one in the gap – stopping the slow pointer at the target instead of before it. Why: To remove a node in a singly-linked list, you need the node BEFORE it. Correction: Advance fast $n + 1$ steps from the dummy, so slow stops one before the target.

Problem Mutations

What if you needed to find (not remove) the $n$-th from end? (stress-tests: removal vs access) Same two-pointer gap; just return slow.next.val instead of unlinking.
What if the list were doubly-linked? (stress-tests: singly-linked) Traverse to the end, then go back $n$ steps using prev pointers. $O(n)$, no gap technique needed.
What if $n$ could be larger than the list length? (stress-tests: valid $n$ assumption) Count the list length first, or detect when fast goes null before the gap is established. Return head unchanged if $n$ is invalid.

AI usage disclosure Claude Opus 4.6 · content enrichment

Standardised annotation dropdowns for Remove Nth Node From End of List generated via batch canonical enrichment pass. Review against personal solving experience.

Delete Node in a Linked List (237)

This was a little simpler than expected, we just need to copy over one time and skip the one after the node-to-be-removed. This makes it a single action only.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
   # Definition for singly-linked list.
   # class ListNode:
   #     def __init__(self, x):
   #         self.val = x
   #         self.next = None

   class Solution:
     def deleteNode(self, node):
       """
         :type node: ListNode
         :rtype: void Do not return anything, modify node in-place instead.
         """
       node.val = node.next.val
       node.next = node.next.next

Code Snippet 18: Delete Node in a Linked List (237)

Pattern Extraction

Core Insight: You don’t have access to the previous node, so you can’t unlink the target node. Instead, copy the next node’s value into the target and skip the next node. Pattern Name: Value Overwrite Deletion Canonical Section: Linked List > Deletion Recognition Signals:

“Delete a node” with only access to that node (not its predecessor)
Not the tail node (guaranteed)

Anti-Signals:

Have access to the predecessor – standard deletion (redirect predecessor’s next)
Need to delete the tail – can’t use value copy (nothing to copy from)

Decision Point: No predecessor access = value copy trick. Predecessor access = standard pointer redirect.

Pitfalls and Misconceptions

Trap: Trying to actually remove the node from the list. Why: Without the predecessor, you can’t redirect the pointer TO this node. You can only change what this node IS. Correction: node.val = node.next.val; node.next = node.next.next. The node effectively becomes its successor.

Problem Mutations

What if the node were the tail? (stress-tests: non-tail guarantee) Can’t use this trick (node.next is null, nothing to copy from). Would need the predecessor.
What if the list were doubly-linked? (stress-tests: singly-linked) Can access predecessor via node.prev. Standard deletion: node.prev.next = node.next; node.next.prev = node.prev.

AI usage disclosure Claude Opus 4.6 · content enrichment

Batch annotation for Delete Node in a Linked List.

TODO Odd Even Linked List (328)

Advanced Pointer Structures #

Working with random pointers or multi-level pointers
Flatten multilevel doubly linked lists

Problems #

LRU Cache (146)

Pythonic way is to just use OrderedDict, updating the freshness can be done using move_to_end() and popping can be done using popitem(last=False)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
   from collections import OrderedDict
    class LRUCache:

        def __init__(self, capacity: int):
            self.store = OrderedDict()
            self.max = capacity
            self.cap = 0

        def get(self, key: int) -> int:
            if key not in self.store:
                return -1

            # register as used:
            self.store.move_to_end(key)
            return self.store[key]


        def put(self, key: int, value: int) -> None:
            # shift usage if pre-existing:
            if key in self.store:
                self.store.move_to_end(key)

            self.store[key] = value
            if (len(self.store) > self.max):
                # evicts LRU item:
                self.store.popitem(last=False)



    # Your LRUCache object will be instantiated and called as such:
    # obj = LRUCache(capacity)
    # param_1 = obj.get(key)
    # obj.put(key,value)

Code Snippet 19: LRU Cache (146) – using OrderedDict

A manual implementation for this would be: keep track of the relative ordering of things (doubly linked list [i.e. fwd and back]) and a hashmap for a reference to the nodes that we should jump to. They only restrict runtime, not space.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
    class Node:
        def __init__(self, key, val):
            self.key = key
            self.val = val
            self.prev = self.next = None

    class LRUCache:
        def __init__(self, capacity: int):
            self.capacity = capacity
            self.cache = {}  # key -> node
            # Dummy head and tail nodes
            self.head, self.tail = Node(0, 0), Node(0, 0)
            self.head.next, self.tail.prev = self.tail, self.head

        def _remove(self, node):
            prev, nxt = node.prev, node.next
            prev.next, nxt.prev = nxt, prev

        def _add(self, node):
            prev, nxt = self.tail.prev, self.tail
            prev.next = nxt.prev = node
            node.prev, node.next = prev, nxt

        def get(self, key: int) -> int:
            if key not in self.cache:
                return -1
            node = self.cache[key]
            # easier to remove and add to get the LRU part handled
            self._remove(node)
            self._add(node)
            return node.val

        def put(self, key: int, value: int) -> None:
            if key in self.cache:
                self._remove(self.cache[key])
                node = Node(key, value)
                self.cache[key] = node
                self._add(node)
            if len(self.cache) > self.capacity:
                # Remove from head
                lru = self.head.next
                self._remove(lru)
                del self.cache[lru.key]

Code Snippet 20: LRU Cache (146) – without using OrderedDict

Pattern Extraction

Core Insight: Combine a hash map (for $O(1)$ key lookup) with a doubly-linked list (for $O(1)$ recency reordering and eviction). The hash map stores key-to-node pointers; the list maintains access order. Pattern Name: Hash Map + Doubly-Linked List (OrderedDict) Canonical Section: Linked List > Design Problems Recognition Signals:

Data structure with $O(1)$ get, put, and eviction
“Least recently used” eviction policy (access order matters)
Need both fast lookup AND fast reordering

Anti-Signals:

“Least frequently used” (LFU) – needs frequency tracking + recency within frequency groups. Connects to LC 460 LFU Cache
No eviction needed – just a hash map
Eviction by TTL (expiry time) – different structure (sorted set by expiry time)

Decision Point: LRU = hash map + doubly-linked list (or Python OrderedDict). LFU = hash map + frequency buckets. The eviction policy determines the data structure. Interviewer Comms: “I combine a hash map mapping keys to doubly-linked-list nodes, with the list maintaining recency order. get moves the node to the tail (most recent). put adds at the tail and evicts from the head (least recent) if over capacity. All operations $O(1)$ thanks to hash map + list pointers.”

Pitfalls and Misconceptions

Trap: Using a singly-linked list instead of doubly-linked. Why: Removing a node from the middle of a singly-linked list requires finding its predecessor ($O(n)$). A doubly-linked list allows $O(1)$ removal. Correction: Use a doubly-linked list with prev and next pointers.
Trap: Not using sentinel (dummy) head and tail nodes. Why: Without sentinels, adding to an empty list and removing the last element require special cases. Correction: Create dummy head and tail nodes that always exist. Real nodes go between them.
Trap: Forgetting to delete the evicted key from the hash map when evicting. Why: The hash map retains a stale entry pointing to a removed node, causing incorrect lookups. Correction: When evicting: del self.cache[lru.key]. The node must store its key to enable this reverse lookup.

Problem Mutations

What if the eviction policy were LFU (least frequently used) instead of LRU? (stress-tests: eviction policy) Need a more complex structure: frequency buckets (each bucket is a doubly-linked list), plus a hash map from key to node. Connects to LC 460 LFU Cache.
What if the cache had TTL (time-to-live) per entry? (stress-tests: recency-based eviction) Need a priority queue (min-heap) keyed by expiry time, combined with a hash map. Expired entries are lazily removed on access.
What if get and put needed to be thread-safe? (stress-tests: single-threaded assumption) Need a lock (mutex) around get/put, or a concurrent hash map + concurrent linked list. This is a common system design follow-up.
What if capacity could change dynamically? (stress-tests: fixed capacity) Increasing capacity is trivial. Decreasing requires evicting excess entries immediately.

AI usage disclosure Claude Opus 4.6 · content enrichment

Standardised annotation dropdowns for LRU Cache generated via batch canonical enrichment pass. Review against personal solving experience and adjust.

Copy List with Random Pointer (138)

Like a tumour, we just interleave the new nodes along with the existing nodes, then once the grafting is all done, we just skip them over, and only accepting the newly created nodes.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
    class Solution:
        def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
            if not head:
                return None

            # 1. Interleave copied nodes with originals
            curr = head
            while curr:
                copy = Node(curr.val, curr.next)
                curr.next = copy
                curr = copy.next

            # 2. Assign random pointers for the copied nodes
            curr = head
            while curr:
                copy = curr.next
                copy.random = curr.random.next if curr.random else None
                curr = copy.next

            # 3. Separate the original and copied lists
            curr = head
            copy_head = head.next
            while curr:
                copy = curr.next
                curr.next = copy.next
                copy.next = copy.next.next if copy.next else None
                curr = curr.next

            return copy_head

Code Snippet 21: Copy List with Random Pointer (138)

This works too (my styles), but it’s slower because of the extra space used:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
    class Solution:
        def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
            if not head:
                return None
            old_to_new = {}
            curr = head
            while curr:
                old_to_new[curr] = Node(curr.val)
                curr = curr.next
                curr = head
            while curr:
                old_to_new[curr].next = old_to_new.get(curr.next)
                old_to_new[curr].random = old_to_new.get(curr.random)
                curr = curr.next
            return old_to_new[head]

Code Snippet 22: Copy List with Random Pointer (138) – my style, extra space used

Pattern Extraction

Core Insight: Interleave cloned nodes with originals (A -> A' -> B -> B' -> ...). This lets you set random pointers using original.random.next (which is the clone of the random target). Then separate the two lists. Alternatively, use a hash map from original to clone ($O(n)$ space but simpler). Pattern Name: Interleaved Cloning (O(1) Space Deep Copy) / Hash Map Deep Copy Canonical Section: Linked List > Design Problems Recognition Signals:

Deep copy a linked list with an extra pointer (random, arbitrary)
$O(1)$ extra space (interleaving) or $O(n)$ space (hash map)
Three-pass approach for interleaving: clone, set random, separate

Anti-Signals:

$O(n)$ space is fine – hash map approach is much simpler
The extra pointer is always to the next node or null – no special handling needed

Decision Point: Hash map approach ($O(n)$ space) is cleaner for interviews. Interleaving ($O(1)$ space) is the clever optimisation. Know both; present the hash map approach unless space is constrained.

Pitfalls and Misconceptions

Trap: Using the hash map approach but forgetting to handle None random pointers. Why: node.random can be None. Accessing clone_map[None] causes a KeyError. Correction: Check if node.random: clone.random = clone_map[node.random].
Trap: In the interleaving approach, not correctly separating the two lists at the end. Why: If you don’t restore original.next pointers, the original list is corrupted. Correction: Third pass: original.next = original.next.next; clone.next = clone.next.next if clone.next else None.

Problem Mutations

What if the structure were a graph (multiple outgoing pointers)? (stress-tests: linked list structure) Same idea: BFS/DFS with a hash map from original to clone. Connects to LC 133 Clone Graph.
What if random pointers could point to nodes in a different list? (stress-tests: self-referential) The clone’s random pointers would need to map to nodes in the other list. The hash map approach handles this naturally.
What if the list were circular? (stress-tests: linear list) Need cycle detection during traversal to avoid infinite loops. The hash map doubles as a visited set.

AI usage disclosure Claude Opus 4.6 · content enrichment

Standardised annotation dropdowns for Copy List with Random Pointer generated via batch canonical enrichment pass. Review against personal solving experience.

TODO Flatten Multilevel Doubly Linked List (430)

SOE #

Careful on the return type for trivial failures, it’s sometimes just return nothing.
Null pointer dereference and empty list edge cases
Failing to reset pointers after cycle detection
Mishandling dummy node initialization and cleanup
Off-by-one errors in pointer movement or loop boundaries
NOT saving before assigning, save all temps before any assignments.
PYTHON GOTCHA: Forgetting that the use of heapq requires us to handle duplicates by providing some tie-breaker for tuple comparisons.

Reversal Specific #

Losing the reference to next before reassigning curr.next: always save next_node = curr.next BEFORE any pointer mutation.
Forgetting to return the new head after reversal (the old tail). This is especially easy to miss in partial-reversal problems (Reverse Nodes in K-Group, Reverse Between).

Dummy Node Errors #

Creating the dummy but forgetting to connect it: dummy.next = head must be set explicitly.
Returning dummy instead of dummy.next.

AI usage disclosure Claude Opus 4.6 · content enrichment

SOE entries from common linked list reversal and dummy node mistakes. Review and adjust.

Decision Flow #

Need reversal/segment reorder? → Iterative or recursive reversal approaches
Detect cycle or intersection? → Use slow/fast pointer patterns
Check palindrome or split list? → Find middle → reverse → compare
Merge or sort? → Bottom-up mergesort or merge strategies
Handling advanced pointers? → Use hash map or recursion

Styles, Tricks and Boilerplate #

Styles #

I like the idea of using walrus operators for the while loops when handling linked list questions, example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
  # Definition for singly-linked list.
  # class ListNode:
  #     def __init__(self, val=0, next=None):
  #         self.val = val
  #         self.next = next
  class Solution:
      def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
          if (not head) or (head and not head.next):
              return head

          dummy = ListNode()
          prev = dummy
          ptr = head
          while (first:=ptr) and (second:=ptr.next):
              next_join = second.next
              second.next = first
              first.next = next_join
              prev.next = second
              prev = first
              ptr = next_join

              return dummy.next

Code Snippet 23: Flatten Multilevel Doubly Linked List (430)

When building a linked list from multiple others, it’s useful to just a dummy node and “consume” from providers of values.
Tortoise & Hare:
- if faster pointer is valid, then the slower pointer will be too
The two pointer trick to determine the intersecting node is pretty nifty too. See Problem number (160).

Topic 6: Linked List

Canonical Questions #

Pointer Reversal & Reordering #

Problems #

Merging & Sorting #

Problems #

Cycle & Intersection Detection #

Problems #

Half-Point & Palindromic Checking #

Problems #

Linked List Arithmetic & Representation #

Problems #

Structural Manipulation & Deletion #

Problems #

Advanced Pointer Structures #

Problems #

SOE #

Reversal Specific #

Dummy Node Errors #

Decision Flow #

Styles, Tricks and Boilerplate #

Styles #

Tricks #

TODO KIV #

[ ] from existing canonicals #

[ ] merging and sorting: TODO Sort List (148) #

[ ] cycle & intersection detection:: TODO Linked List Cycle II (142) #

[ ] half point and palindrome checking:: TODO Palindrome Linked List (234) #

[ ] linked list arithmetic:: TODO Add Two Numbers II (445) #

[ ] Structural manipulation and deletion :: TODO Odd Even Linked List (328) #

[ ] Advanced Pointer Structures :: TODO Flatten Multilevel Doubly Linked List (430) #