DSA sheet · Linked List · Basic operations pattern

Search & Insert in Linked List

The second video of the basic operations pattern. The teacher shows how to search for a value in a linked list and how to insert a new node in the three possible places: at the beginning, in between, and at the end. Search and insert-at-end are solved both with a loop and with recursion. These are the moves that every harder problem is built from: walking with an alias pointer, choosing the right loop condition (curr vs curr.next), and saving the next node before you break a link.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run (table + drawings) → ⑨ complexity & remember

• Part 0 · Linked lists from scratch
• Part A · Search with a loop
• Part B · Search with recursion
• Part C · Insert at the beginning
• Part D · Insert in between (after k nodes / after a value)
• Part E · Insert at the end with a loop
• Part F · Insert at the end with recursion
• Part G · Revision page

Part 0 · Linked lists from scratch

What is a node?

A linked list is a chain of nodes. Each node is a small box holding two things: val (its data) and next (a link to the next node). The nodes can live anywhere in memory; each node simply remembers where the next one is. The last node's next is None, meaning "nothing after me".

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

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

The head is the first node. Every other node is reachable from it, so "the list" and "the head" mean the same thing: functions take the head and return the head.

Walking, and why there's no index

We move one step with curr = curr.next. There is no list[i]: to reach position i you must take i steps from the head, which costs O(i), up to O(n). Array cells sit side by side, so an array can jump straight to index i; list nodes are scattered, so we can only follow the links.

Rule 1: never move head; use an alias

The teacher repeats this in this video: the head is your only handle on the list. There is no index to fall back on, so if head moves forward and nothing else points at the first node, the front of the list is lost for good. So we make a second name for the same node, curr = head, and move curr instead.

Rule 2: save next before you change a pointer

A node knows only its own next. If you overwrite a.next and nothing else points at the old next node, that node and everything after it are unreachable. So before rewiring a .next, store the old value in a variable (the teacher calls it temp). Part D is where this matters.

Recursion on lists (Parts B and F)

A list is "one node + a smaller list" (the rest, starting at head.next). A recursive function handles the current node, then calls itself on head.next. Each call has its own head variable saved on the call stack, so the teacher says we don't need an alias in recursion: each call remembers its own head, and when the calls return, the first call still has the original head. The price is extra memory for the stack: one waiting call per node.

The teacher's tip about linked list complexity

In linked list problems, the answer is almost always linear. A brute force usually walks the list two or three times (O(2n) or O(3n)), and the optimised version walks it once, or even half of it (O(n) or O(n/2)). O(n²) solutions are rare here. With up to 10⁵ nodes, a linear walk is safe: about 10⁸ operations is where TLE becomes a risk, and at 10⁹ it is certain.

Part A · Search with a loop

GFG "Search in Linked List"

1The question in simple words

You are given the head of a list and a number key. Return True if some node holds key, otherwise False.

[1] → [2] → [3] → [4] → [5] → None

key = 4 → True        key = 6 → False

GFG also passes the length n as a parameter; we don't need it, because the None at the end tells us when to stop.

2What the constraints tell us

• Up to 10⁵ nodes → one pass, O(n), is about 10⁵ steps. Safe.
• There's no index, so we can't do anything cleverer like binary search. We simply have to look at the nodes one by one.

3Intuition

Put your finger on the first node. Read its value. If it's the key, you're done. If not, slide your finger to the next node. Keep going. If your finger falls off the end (lands on None), the key isn't in the list.

4Building the logic from the examples

The alias

We'll walk the list, so we don't use head itself. curr = head.

Search for 4

At 1: is 1 the key? No → curr = curr.next. At 2: no. At 3: no. At 4: yes → return True.

Search for 6: where must the walk stop?

1, 2, 3, 4, 5: no match. Then curr = curr.next puts curr on None. If we kept going, we'd read None.val or None.next, which crashes (the teacher calls it a null pointer exception). So the loop runs only while curr is a real node: while curr is not None.

When the loop ends this way, we've checked every node without a match → return False, written after the loop.

5Approach steps

1. curr = head.
2. While curr is not None: if curr.val == key, return True; else move curr = curr.next.
3. After the loop, return False.

6Code (Python)

class Solution:
    def searchKey(self, head, key):
        curr = head                    # alias: head stays where it is
        while curr is not None:        # stop before touching None
            if curr.val == key:
                return True            # found it
            curr = curr.next           # move one node ahead
        return False                   # walked off the end: not there

7Code line by line

8Dry run

List 1 → 2 → 3 → 4 → 5.

[1] → [2] → [3] → [4] → [5] → None
                   ↑
                  curr  ✓

[1] → [2] → [3] → [4] → [5] → None
                               ↑
                              curr (loop stops)

9Complexity & remember

• Time O(n): in the worst case (key missing or at the end) we visit every node once. For 10⁵ nodes that's safe.
• Space O(1): just the curr pointer.

Part B · Search with recursion

1The question in simple words

Same as Part A: is key anywhere in the list?

2What the constraints tell us

• Time: still one visit per node.
• Python note (my addition): one waiting call per node means the stack can be 10⁵ calls deep. Python's default limit is about 1000, so on a really long list this version raises RecursionError. Use the loop in real submissions; learn this one for practice.

3Intuition

"Is the key in this list?" can be split into two smaller questions: is it in this node? If not, is it in the rest of the list? The rest of the list is just another list, starting at head.next, so we ask the same function about it.

4Building the logic

No alias needed

In the loop, curr = curr.next moved us. In recursion, we "move" by passing head.next as the argument of the next call. Each call has its own head, so the original head is never disturbed.

The match case

if head.val == key: return True. Otherwise return searchKey(head.next, key). The key stays the same; only the starting node moves.

The base case: the loop condition, flipped

Search for 6: calls on 1, 2, 3, 4, 5, then a call on 5.next, which is None. That call must not read .val (crash). The teacher's way to find the base case: the loop ran while curr was not None, so the recursion stops when head is None. Reaching None means we went past the end without a match → return False.

5Approach steps

1. If head is None → return False.
2. If head.val == key → return True.
3. Otherwise → return the answer for head.next.

6Code (Python)

class Solution:
    def searchKey(self, head, key):
        if head is None:                       # walked past the end
            return False
        if head.val == key:                    # found in this node
            return True
        return self.searchKey(head.next, key)  # ask about the rest

7Code line by line

8Dry run

List 1 → 2 → 3 → 4 → 5. "f(x)" = a call whose head is node x.

Newest call on top (red). Each call returns the same True/False it received, and leaves the stack.

9Complexity & remember

• Time O(n): each node is visited at most once, same as the loop.
• Space O(n): the waiting calls on the stack. That's why the teacher calls the loop the better solution, while still practising recursion.

Part C · Insert at the beginning

The teacher lists three kinds of insertion: at the beginning, in between, and at the end. She explains the first two on the board (with a loop), then codes the third both ways.

1The question in simple words

Add a new node with value x in front of the current first node, and return the new head.

before:        [1] → [2] → [3] → [4] → None
insert 5:  [5] → [1] → [2] → [3] → [4] → None
            ↑
          new head

2What the constraints tell us

• No walking is needed at all, so the list length doesn't matter: this is O(1).
• The list may be empty. Then the new node simply becomes the only node (the code below handles that without a special case).

3Intuition

To join a queue at the front, you stand in front of the first person and point at them ("you're after me"). Then everyone agrees you are now the front.

4Building the logic

1. Make the node: node = ListNode(x). Right now it's alone: [5] → None.
2. Point it at the old first node: node.next = head. Now [5] → [1] → [2] → ….
3. But if we return head now, we return node 1, and the list we hand back is 1 → 2 → 3 → 4. Node 5 isn't included, because nothing points to 5 and we can't walk backwards. So, last step: make the new node the head: head = node, then return it.

5Approach steps

1. Make the new node.
2. Set its next to the current head.
3. Return the new node as the head.

6Code (Python)

class Solution:
    def insertAtBeginning(self, head, x):
        node = ListNode(x)      # the new node, alone for now
        node.next = head        # link it in front of the old first node
        head = node             # the new node is now the head
        return head

7Code line by line

8Dry run: insert 5 into 1 → 2 → 3 → 4

after step 2:          after step 3:
[5] → [1] → [2] …      [5] → [1] → [2] …
 ↑     ↑                ↑
node  head             head

9Complexity & remember

• Time O(1), space O(1): no walking, three pointer moves.

Part D · Insert in between

1The question in simple words

Insert a new node somewhere inside the list. The teacher says the position can be described in two ways, and both are solved the same way:

• by a count: "insert after the first k nodes" (e.g. after 2 nodes), or
• by a value: "insert after the node whose value is 2".

before:          [1] → [2] → [3] → [4] → None
insert 5 after 2 nodes (or after value 2):
                 [1] → [2] → [5] → [3] → [4] → None

2What the constraints tell us

• We must walk to the spot, so it's O(n) in the worst case, fine for 10⁵ nodes.
• The teacher doesn't discuss bad positions. My additions: k = 0 means "before everything", which is Part C; k larger than the length has no such spot, so the code below leaves the list unchanged instead of crashing. k = length works as "insert at the end".

3Intuition

To add a link in the middle of a chain: hold the far half in one hand first, then open the link, hook in the new piece, and connect the new piece to the far half. If you open the link without holding the far half, it falls away.

4Building the logic

Walking to the spot with a counter

We want curr to stand on the k-th node (node 2 for k = 2), because the new node goes right after it.

The teacher first writes the loop as while count <= 2, then checks it by hand and corrects it. Start with curr = head and count = 1 (we're already standing on node number 1):

• count = 1, is 1 < 2? Yes → move to node 2, count = 2.
• count = 2, is 2 < 2? No → stop. curr is on node 2 ✓.

With <=, the loop would run once more and stop on node 3, one node too far. So the condition is count < k with count starting at 1. We only need to move k − 1 times.

The wrong way to hook in the new node

curr is on 2. If we write curr.next = node straight away:

[1] → [2] → [5] → None

      [3] → [4] → None      ← nothing points here any more: LOST

Printing the list now gives 1 → 2 → 5. 3 and 4 are gone. The teacher's warning: don't break a link until the nodes after it are saved in another variable.

The right way: save, link, reconnect

1. temp = curr.next: hold node 3 (and everything after it).
2. curr.next = node: 2 now points to 5.
3. node.next = temp: 5 now points to 3.

[1] → [2] → [5] → [3] → [4] → None
       ↑     ↑     ↑
     curr  node  temp

5Approach steps

1. If k is 0, insert at the beginning (Part C).
2. curr = head, count = 1. While count < k and curr exists: move curr, count += 1.
3. If curr is None, the position doesn't exist: return head unchanged.
4. temp = curr.next → curr.next = node → node.next = temp.
5. Return head (the head didn't change).

6Code (Python)

class Solution:
    def insertAfterK(self, head, k, x):
        if k == 0:                        # before everything = insert at head
            node = ListNode(x)
            node.next = head
            return node
        curr = head
        count = 1                         # we're standing on node number 1
        while curr is not None and count < k:
            curr = curr.next              # walk to the k-th node
            count += 1
        if curr is None:                  # list shorter than k: no such spot
            return head
        node = ListNode(x)
        temp = curr.next                  # 1. save the rest of the list
        curr.next = node                  # 2. k-th node -> new node
        node.next = temp                  # 3. new node -> the saved rest
        return head

    def insertAfterValue(self, head, target, x):
        curr = head
        while curr is not None and curr.val != target:
            curr = curr.next              # walk until we stand on target
        if curr is None:                  # target not in the list
            return head
        node = ListNode(x)
        temp = curr.next
        curr.next = node
        node.next = temp
        return head

The k = 0 branch and the "list too short" check are my additions; the teacher's board version assumes a valid position.

7Code line by line

8Dry run: insert 5 after k = 2 nodes in 1 → 2 → 3 → 4

[1] → [2] → [3] → [4] → None
       ↑     ↑
     curr  temp        [5] → None
                        ↑
                       node

[1] → [2] → [5] → None
       ↑     ↑
     curr  node

            [3] → [4] → None
             ↑
            temp (still safe)

[1] → [2] → [5] → [3] → [4] → None
 ↑
head (returned)

9Complexity & remember

• Time O(k), which is O(n) in the worst case: walking to the spot. The rewiring itself is O(1).
• Space O(1).

Part E · Insert at the end with a loop

GFG "Linked List Insertion At End"

1The question in simple words

Add a node with value x after the current last node. Return the head.

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

2What the constraints tell us

• Up to 10⁵ nodes → walking to the end once is O(n), safe.
• The number of nodes can be 0. The teacher points this out from the constraints: then head is None, and the new node is the whole list. We must handle this first, because the walking loop reads curr.next, which would crash on None.

3Intuition

Walk to the last coach of the train (the one with nothing behind it) and hook the new coach onto it.

4Building the logic

Where should curr stop?

The new node has to go into the last node's next. So we want curr to stop on node 4, not on the None after it. From None we can't attach anything (we've walked past the node whose next we need to change).

How do we recognise the last node? It's the one whose next is None. So: while curr.next is not None: curr = curr.next.

Trace: at 1, next is 2 → move. At 2 → move. At 3 → move. At 4, next is None → stop. Now curr.next = node, and return head.

5Approach steps

1. Make the new node.
2. If head is None, return the new node.
3. curr = head; while curr.next exists, move curr.
4. curr.next = node; return head.

6Code (Python)

class Solution:
    def insertAtEnd(self, head, x):
        node = ListNode(x)
        if head is None:               # empty list: new node is the list
            return node
        curr = head
        while curr.next is not None:   # stop ON the last node
            curr = curr.next
        curr.next = node               # last node -> new node
        return head

7Code line by line

8Dry run: insert 5 at the end of 1 → 2 → 3 → 4

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

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

[1] → [2] → [3] → [4] → [5] → None
 ↑                 ↑     ↑
head              curr  node

Empty list: head is None → return [5] → None straight away.

9Complexity & remember

• Time O(n): we walk to the last node once.
• Space O(1): only a few variables (the teacher's words: a few variables don't count as extra space).

Part F · Insert at the end with recursion

The teacher asks us to try this one ourselves first, then builds it with a call stack.

1The question in simple words

Same as Part E: add x after the last node, return the head.

2What the constraints tell us

• 0 nodes allowed → the recursion must handle head = None. Nicely, the base case below does exactly that.
• Up to 10⁵ nodes → 10⁵ waiting calls. Again, too deep for Python's default limit; the loop is the practical choice.

3Intuition

Each call says to the next one: "add x at the end of your list (the rest after me) and give me back that list's head. I'll hang it on my next." The call that receives an empty list knows exactly what to do: the answer is just the new node.

4Building the logic

The base case: what happens at None?

The calls go 1 → 2 → 3 → 4 → None. In the loop, the end was where we attached the node, so the recursion stops when head is None.

What should it return? The teacher first asks the class: return None? Think about where the returned value goes: into the previous node's next. Returning None would just store None again, and the new node would never be added. Instead: we're standing exactly where the new node belongs, so create it here and return it: return ListNode(x).

Catching the returned value

The call for node 4 receives node 5. It must connect them: head.next = insertAtEnd(head.next, x). So the recursive call isn't just "returned"; its result is stored in head.next.

What each normal call returns

After node 4 links to 5, the call for node 3 is waiting to set 3.next. It needs node 4 back, so every call finishes with return head. In the end, the call for node 1 returns node 1, the head of the full list.

5Approach steps

1. If head is None → return a new node with x.
2. Otherwise → head.next = insertAtEnd(head.next, x).
3. Return head.

6Code (Python)

class Solution:
    def insertAtEnd(self, head, x):
        if head is None:                              # the spot after the last node
            return ListNode(x)                        # create the new node right here
        head.next = self.insertAtEnd(head.next, x)    # catch the rest and hang it on me
        return head                                   # give my node back to my caller

7Code line by line

8Dry run: insert 5 at the end of 1 → 2 → 3 → 4

after step 6:   [1] → [2] → [3] → [4] → [5] → None
                                   ↑
                             f(4)'s head (returned to f(3))

Empty list: the very first call has head = None → returns [5]. Correct, with no extra check needed.

9Complexity & remember

• Time O(n): one call per node.
• Space O(n): the call stack (the teacher: "internal memory"). The loop version uses O(1), so it's better here.

Part G · 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

s = Solution()
# with the search solution:
# print(s.searchKey(build([1, 2, 3, 4, 5]), 4))   # True
# print(s.searchKey(build([1, 2, 3, 4, 5]), 6))   # False
# with the insert-at-end solution:
# print(to_list(s.insertAtEnd(build([1, 2, 3, 4]), 5)))   # [1, 2, 3, 4, 5]
# print(to_list(s.insertAtEnd(None, 5)))                  # [5]

Based on this video: Search & Insert in Linked List | iterative & recursive