DSA sheet · Linked List · concept video

Linked List Patterns Overview

This is the map for the whole linked list section. Before any coding, the teacher answers two questions: what is a linked list, and why do we need it when we already have arrays? Then she walks through the five patterns that she says cover the linked list questions asked in interviews: basic traversal, fast & slow pointers, reversal, linked list + stack, and merge / sort. For each one she shows the idea on a small drawing and names the problems that use it. These notes add a small, tested Python template for every pattern, so that each later page feels familiar.

This page adapts the usual order for a concept video:
① what a linked list is → ② array vs linked list → ③ each pattern: the idea → when to spot it → intuition → building it from her example → steps → Python template → line by line → dry run → complexity & remember → ④ which sheet problems use which pattern → ⑤ revision

• Part 0 · What a linked list is
• Part A · Array vs linked list: why we need it
• Part B · Pattern 1: basic traversal
• Part C · Pattern 2: fast & slow pointers
• Part D · Pattern 3: reversal with three pointers
• Part E · Pattern 4: linked list + stack
• Part F · Pattern 5: merge & sort
• Part G · Two extra tools the sheet uses (dummy node, recursion)
• Part H · Which sheet problem uses which pattern
• Part I · Revision page

Part 0 · What a linked list is

Linear vs non-linear data structures

The teacher starts here, because it tells us what kind of thing a linked list is.

So a linked list is a linear data structure: items in a row, each leading to exactly one next item.

The node

A linked list is made of nodes. Each node holds two things:

• a value (the data), and
• a next pointer: the memory address of the next node. If there is no next node, it holds null (None in Python), meaning "the chain ends here".

In the drawing, the address is shown as an arrow:

[1] → [2] → [3] → [4] → None
 ↑
head

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val      # the data
        self.next = next    # the next node, or None at the end

Head, walking, no index

• head: a pointer to the first node. Everything is reached from it.
• Walking: curr = curr.next moves one node forward (head.next "means" the node 2 in the picture).
• No indexing: the teacher stresses that you can't jump to "the 3rd element" like in an array or string. To reach position i you walk i steps, which is O(n) in the worst case.
• One direction only: from node 2 you can go to 3, but never back to 1, because nothing in node 2 points backwards.

Save next before you change a pointer

A node is reachable only through the arrow that points to it. If you overwrite a.next while nothing else points to the old next node, that node and everything after it are lost. So store the old next in a variable before rewiring. You'll see this rule again and again: in insertion, and above all in reversal (Pattern 3).

Part A · Array vs linked list: why we need it

Arrays are very useful, but the teacher lists three problems with them. Each one is a reason linked lists exist.

1Problem 1: an array needs one unbroken block of memory

All array items sit side by side. A linked list's memory is dynamic: each node can be anywhere in memory, because every node carries the address of the next one. The nodes are tied together by those addresses, not by being neighbours.

2Problem 2: an array's size is fixed

Once a (classic) array's size is set, it can't change. A linked list just keeps adding new nodes, so its size grows and shrinks freely.

(Python's list hides this by quietly copying itself into a bigger block when it fills up, but the "one block" rule still holds underneath.)

3Problem 3: inserting and deleting in an array is costly

Her example: the array [1, 2, 3, 4] (indices 0 to 3). Delete the 1. Now there's a hole at index 0, so every later item must shift one place: 2 to index 0, 3 to index 1, 4 to index 2.

index:   0   1   2   3
before: [1] [2] [3] [4]
delete 1, then shift everything:
after:  [2] [3] [4]        ← n − 1 moves → O(n)

Insertion has the same cost: to make room, items shift the other way. So insert and delete in an array are O(n).

In a linked list, nothing shifts. Her example: insert 5 between 1 and 2. Make node 5, point 5.next at 2, and point 1.next at 5. Two arrows change, nothing else moves → O(1).

before:  [1] → [2] → [3] → [4] → None

after:   [1] → [5] → [2] → [3] → [4] → None
          1.next changed      5.next = old 1.next

Part B · Pattern 1: basic traversal

The teacher calls this the very first pattern: once you know it, you can move on to the others.

1The idea in simple words

Traversal means visiting the nodes one by one, from the head to the end, and doing some work at each node: counting them, finding the length, finding a value, inserting a node at a position, deleting a node at a position.

2When to use it

• Any question that needs to "look at every node" or "reach position k".
• Because there is no indexing, this walk is how you reach anything.

3Intuition

A finger starts on the head and keeps hopping along the arrows until it lands on None. Each hop is head = head.next.

4Building it from her example: counting nodes

List 1 → 2 → 3 → 4. We loop while the pointer isn't None, adding 1 to a counter for each node and then hopping forward. When the pointer becomes None, we stop, and the counter holds the length.

Her warning about where count starts

She counts the jumps: from 1 to 2 is one jump, 2 to 3 two jumps, 3 to 4 three jumps. But there are four nodes. If you count jumps (that is, you stop when you are standing on the last node), a counter that starts at 0 ends at 3, one short. In that style you must start count at 1 (the node you're already standing on).

5Steps

1. count = 0, curr = head.
2. While curr is not None: count += 1, curr = curr.next.
3. Return count.

6Python template

def length(head):
    count = 0
    curr = head                 # walk with a copy, keep head safe
    while curr is not None:     # stop after the last node
        count += 1              # one more node seen
        curr = curr.next        # hop to the next node
    return count

def length_by_jumps(head):
    if head is None:            # this style can't handle an empty list
        return 0
    count = 1                   # the node we're standing on
    curr = head
    while curr.next is not None:    # stop ON the last node
        curr = curr.next
        count += 1              # one more jump = one more node
    return count

7Line by line

8Dry run on 1 → 2 → 3 → 4

9Complexity & remember

• Time O(n), space O(1).

Part C · Pattern 2: fast & slow pointers

1The idea in simple words

The teacher links this to the two-pointer approach from arrays, with a twist: both pointers start together, but they move at different speeds. slow takes one step at a time; fast takes two. So slow always covers half the distance that fast covers.

2When to use it

• Finding the middle of the list in one pass.
• Detecting a cycle (a list whose last node points back into the list instead of to None).
• (Later on the sheet, related ideas: start of a cycle, n-th node from the end, palindrome, twin sums, reorder list.)

3Intuition

Two runners on a track start at the same line. One runs twice as fast. When the fast runner reaches the finish line, the slow one is exactly halfway. And if the track is a loop, the fast runner will eventually come up behind the slow one and catch them.

4Building it from her examples

Use 1: the middle

List 1 → 2 → 3. Both start on 1. After one move: slow on 2, fast on 3. Fast has reached the end, and slow is on 2, the middle. That's no accident: slow runs at half speed, so it has covered half of what fast covered.

When to stop: fast jumps two nodes (fast.next.next), so both fast and fast.next must exist, otherwise we'd read .next of None. Loop while fast and fast.next.

odd:   [1] → [2] → [3] → None         even:  [1] → [2] → [3] → [4] → None
              ↑     ↑                                        ↑            ↑
            slow  fast (fast.next is None: stop)            slow    fast = None: stop

Use 2: detecting a cycle

Without a cycle, the last node points to None. Fast reaches None first and the loop stops. Slow is always behind, so they never meet.

With a cycle, fast never finds None; it goes round and round. Her example: 1 → 2 → 3 → 4 and 4 points back to 2.

[1] → [2] → [3] → [4]
       ↑           │
       └───────────┘     (4.next is 2, not None)

• After move 1: slow on 2, fast on 3.
• After move 2: slow on 3, fast on 2 (3 → 4 → back to 2).
• After move 3: slow on 4, fast on 4 (2 → 3 → 4). They meet → cycle present.

5Steps

1. slow = fast = head.
2. While fast and fast.next exist: slow one step, fast two steps.
3. Middle: return slow when the loop ends. Cycle: return True the moment slow is fast; if the loop ends, return False.

6Python templates

def middleNode(head):
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next            # 1 step
        fast = fast.next.next       # 2 steps
    return slow                     # second middle when the length is even

def hasCycle(head):
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:            # same node object: they met
            return True
    return False                    # fast hit the end: no cycle

7Line by line

8Dry run: her cycle example (4 → back to 2)

Without the back-arrow (4 → None): move 1 slow 2, fast 3; then fast.next is 4 and fast.next.next is None, so move 2 puts fast on None; the loop ends → False.

9Complexity & remember

• Time O(n), space O(1): just two pointers, no set of visited nodes needed.

Part D · Pattern 3: reversal with three pointers

The teacher rates this one very highly: know reversal well and you can handle about half of all linked list questions.

1The idea in simple words

Normally from 1 you can go to 2, and from 2 to 3, but you can never go back, because the arrows point forward only. Reversing means turning every arrow around, so that someone standing on 3 can only go to 2, not to 4.

before:         [1] → [2] → [3] → [4] → None
after:  None ← [1] ← [2] ← [3] ← [4]
                                  ↑
                              new head

2When to use it

• "Reverse a linked list", "reverse in pairs" (1 2 3 4 → 2 1 4 3), "reverse in groups of k". She names these as very common interview questions.
• Whenever you need to go backwards but must not use extra space (compare with Pattern 4).

3Intuition: the three pointers

• prev: the node behind us; it's where the current node's arrow should point after flipping. At the start there's nothing behind node 1, so prev = None (and that's why 1 ends up pointing to None).
• curr: the node we're standing on, whose arrow we flip now.
• temp (often called next): when we flip curr.next backwards, we lose our only link to the rest of the list. So before flipping, we save it in temp.

4Building it from her example

Standing on 1 (prev = None):

1. Save: temp = curr.next (temp = 2). Otherwise, after the flip, 2 3 4 would be unreachable.
2. Flip: curr.next = prev (1 now points to None).
3. Move prev: prev = curr (prev = 1).
4. Move curr: curr = temp (curr = 2). Now everything before 2 is reversed.

Repeat on 2: save 3, point 2 at 1, prev = 2, curr = 3. Now everything before 3 is reversed. Keep going until curr is None; prev is then on 4, the new head.

Her advice: once you understand these three pointers, you don't need to memorise the code; the steps come naturally.

5Steps

1. prev = None, curr = head.
2. While curr: save, flip, move prev, move curr.
3. Return prev.

6Python template

def reverseList(head):
    prev = None
    curr = head
    while curr is not None:
        temp = curr.next      # 1. save the rest
        curr.next = prev      # 2. flip the arrow backwards
        prev = curr           # 3. prev steps onto curr
        curr = temp           # 4. curr steps onto the saved rest
    return prev               # the old last node is the new head

7Line by line

8Dry run on 1 → 2 → 3 → 4

None ← [1]   [2] → [3] → [4] → None
        ↑     ↑
      prev   curr

None ← [1] ← [2]   [3] → [4] → None
              ↑     ↑
            prev   curr

None ← [1] ← [2] ← [3] ← [4]   None
                          ↑     ↑
                        prev   curr

9Complexity & remember

• Time O(n), space O(1): the list is changed in place.

Part E · Pattern 4: linked list + stack

1The idea in simple words

If we already have the linked list, why bring in a stack? The teacher first explains two words:

• In place: you solve the problem by modifying the list itself (like reversal), with no extra data structure → O(1) extra space.
• Not in place: you copy values into an extra structure, such as a stack, and work there → O(n) extra space.

A stack is last-in, first-out: you push items on top and pop from the top. If you push the list's values from left to right, they pop out right to left. That is "walking backwards" without touching the list.

2When to use it (her two signals)

• You need to come back (go right to left), you'd otherwise have to reverse the list, and extra space is allowed → think stack.
• You need to backtrack: you've already moved 1 → 2 → 3 and now realise you must go back and check something → think stack.

3Intuition

Sticky notes on a pile: walk the list writing one value per note and dropping it on the pile. Then take notes off the top: you're reading the list backwards.

4Building it from her example: adding two numbers

Two lists each hold the digits of a number, most significant digit first. Add them and return the sum as a list.

head1: [1] → [2] → [3] → [4] → None      (the number 1234)
head2: [6] → None                        (the number 6)
answer: [1] → [2] → [4] → [0] → None     (1240)

We can't add 1 and 6 at the heads; addition starts from the right (units digit). To reach 4 we walk to the end. Say 4 + 6 = 10: we write 0 and carry 1 to the left. But in a linked list we can't move left without reversing. That's the moment to use stacks.

1. Walk list 1 and push every value: stack1 = [1, 2, 3, 4] (4 on top).
2. Walk list 2: stack2 = [6].
3. Pop 4 and 6: 4 + 6 = 10 → digit 0, carry 1.
4. Stack2 is empty. Pop 3: 3 + carry 1 = 4 → digit 4, carry 0.
5. Pop 2 → digit 2. Pop 1 → digit 1.
6. Digits came out as 0, 4, 2, 1 (units first). Reverse → 1, 2, 4, 0. That's the answer.

5Steps

1. Push all values of list 1 into stack1, and of list 2 into stack2.
2. While stack1 or stack2 or carry: total = carry + popped values; digit = total % 10; carry = total // 10.
3. Put each digit at the front of the answer list. Return its head.

6Python template

def addTwoNumbers(l1, l2):
    s1, s2 = [], []
    while l1 is not None:          # push list 1, left to right
        s1.append(l1.val)
        l1 = l1.next
    while l2 is not None:          # push list 2
        s2.append(l2.val)
        l2 = l2.next
    head = None
    carry = 0
    while s1 or s2 or carry:       # right to left, like on paper
        total = carry
        if s1:
            total += s1.pop()
        if s2:
            total += s2.pop()
        head = ListNode(total % 10, head)   # new digit goes in front
        carry = total // 10
    return head

7Line by line

8Dry run: 1234 + 6

Top of the stack in red.

9Complexity & remember

• Time O(n + m) (both lists once). Space O(n + m) for the stacks: this is the "not in place" price.

Part F · Pattern 5: merge & sort

1The idea in simple words

The signal is the word sorted: the question says the lists are sorted, or asks you to sort one. Then the merge step from merge sort is the tool: compare the front nodes of two sorted lists, connect the smaller one, move forward, repeat.

2When to use it

• Merge: merge two sorted lists, merge k sorted lists. She notes these are asked often at Amazon and many other big companies.
• Sort: rearrange one list so it ends up sorted (Sort List), or rearrange it in a given order (Reorder List).

3Intuition

Two sorted piles of numbered cards, face up. Always take the smaller of the two top cards and add it to your output pile. When one pile runs out, put the whole other pile on the end; it's already sorted.

4Building it from her example

Lists 1 → 3 → 5 and 2 → 4 → 6, with curr1 on 1 and curr2 on 2.

• 1 vs 2: 1 is smaller → keep 1 connected, move curr1 to 3.
• 3 vs 2: 2 is smaller → connect 2 after 1, move curr2 to 4.
• 3 vs 4: 3 is smaller → connect 3, move curr1 to 5.
• 5 vs 4 → 4; then 5 vs 6 → 5; list 1 runs out → attach the rest (6).

Result: 1 → 2 → 3 → 4 → 5 → 6. Her summary: compare two nodes, see which is smaller, connect it, move forward.

5Steps (merge)

1. dummy = ListNode(0), tail = dummy.
2. While both lists have nodes: attach the smaller front node to tail, advance that list, advance tail.
3. Attach whatever is left of either list. Return dummy.next.

6Python templates

def mergeTwoLists(l1, l2):
    dummy = ListNode(0)              # fake start of the result
    tail = dummy                     # last node of the result so far
    curr1, curr2 = l1, l2
    while curr1 is not None and curr2 is not None:
        if curr1.val <= curr2.val:   # take the smaller front node
            tail.next = curr1
            curr1 = curr1.next
        else:
            tail.next = curr2
            curr2 = curr2.next
        tail = tail.next
    tail.next = curr1 if curr1 is not None else curr2   # leftover is already sorted
    return dummy.next

def sortList(head):
    if head is None or head.next is None:    # 0 or 1 node: already sorted
        return head
    slow, fast = head, head.next             # fast one ahead: slow stops at the FIRST middle
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
    second = slow.next                       # start of the right half
    slow.next = None                         # cut the list in two
    return mergeTwoLists(sortList(head), sortList(second))

7Line by line

8Dry run: merge 1 → 3 → 5 with 2 → 4 → 6

dummy → [1] → [2]
               ↑
              tail
curr1: [3] → [5] → None
curr2: [4] → [6] → None

dummy → [1] → [2] → [3] → [4] → [5] → [6] → None
         ↑
    dummy.next = answer

9Complexity & remember

• Merge: time O(n + m), space O(1) (nodes are reused).
• Sort list: time O(n log n) (log n levels of halving, O(n) merging per level), space O(log n) for the recursion.

Part G · Two extra tools the sheet uses

The teacher's video lists five patterns. These two tools aren't separate patterns in her list, but many sheet problems lean on them, so here they are in one place.

1The dummy node

Many operations treat the head differently: deleting the head, or building a new list where you don't yet know the first node. A dummy node is a fake node placed before the head (dummy.next = head). Now every real node, the head included, has a node in front of it, so one rule handles all of them. At the end, return dummy.next (the real head, which may have changed).

def removeElements(head, val):
    dummy = ListNode(0, head)        # fake node in front of the head
    curr = dummy
    while curr.next is not None:
        if curr.next.val == val:
            curr.next = curr.next.next   # skip it (works for the head too)
        else:
            curr = curr.next
    return dummy.next                # the real head, maybe a new one

remove 1 from  [1] → [2] → [1] → None

dummy → [1] → [2] → [1] → None
 ↑
curr     curr.next is 1 → skip:  dummy → [2] → [1] → None
         then move to [2], skip the last 1 → dummy → [2] → None
answer = dummy.next = [2]

Without the dummy, you'd need a separate loop for "while the head itself has the value". With it, there's no special case.

2Recursion on lists

The teacher solves every problem in the playlist both with a loop and with recursion. The shape is always: base case at None, handle this node, call yourself on head.next. Each call keeps its own head on the call stack. It costs O(n) stack space (and in Python, more than about 1000 nodes hits the recursion limit), so the loop is usually the better submission.

def length_rec(head):
    if head is None:                 # empty list has length 0
        return 0
    return 1 + length_rec(head.next) # this node + the length of the rest

Part H · Which sheet problem uses which pattern

The teacher names some problems herself (marked ★). The rest is my mapping, based on how each problem is usually solved; some problems combine two patterns.

Part I · Revision page

def build(vals):
    head = None
    for v in reversed(vals):
        head = ListNode(v, head)
    return head

def to_list(head):
    out = []
    while head:
        out.append(head.val)
        head = head.next
    return out

print(length(build([1, 2, 3, 4])), length_by_jumps(build([1, 2, 3, 4])))   # 4 4
print(middleNode(build([1, 2, 3])).val, middleNode(build([1, 2, 3, 4])).val)   # 2 3
loop = build([1, 2, 3, 4]); loop.next.next.next.next = loop.next          # 4 -> back to 2
print(hasCycle(loop), hasCycle(build([1, 2, 3, 4])))                    # True False
print(to_list(reverseList(build([1, 2, 3, 4]))))                         # [4, 3, 2, 1]
print(to_list(addTwoNumbers(build([1, 2, 3, 4]), build([6]))))           # [1, 2, 4, 0]
print(to_list(mergeTwoLists(build([1, 3, 5]), build([2, 4, 6]))))        # [1, 2, 3, 4, 5, 6]
print(to_list(sortList(build([4, 1, 3, 2]))))                            # [1, 2, 3, 4]
print(to_list(removeElements(build([1, 2, 1]), 1)), length_rec(build([1, 2, 3])))   # [2] 3

Based on this video: Linked List Patterns | concept overview