Topic 6: Linked List

Canonical Question Types #

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
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
    # iterative version:
    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

    # recursive version:
    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

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

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

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)

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

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

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

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

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

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

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

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.

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

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

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

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

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

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)

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]

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

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]

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.

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

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).

Tricks #

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

Topic 6: Linked List

Canonical Question Types #

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 #

Styles, Tricks and Boilerplate #

Styles #

Tricks #

Decision Flow #

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) #