DSA · Lesson 5 of 9

Linked lists

Nodes and pointers: reversing, finding the middle and detecting cycles.

A linked list is a chain of nodes; each node stores a value and a reference to the next node. Inserting or removing at a known node is O(1), but reaching the k-th item is O(k) because you must walk from the head.

Classic interview techniques:

Reverse by re-pointing each node's next using prev, curr pointers.
Fast/slow pointers — the slow pointer moves 1 step, the fast moves 2: when fast reaches the end, slow is at the middle; if they ever meet, there's a cycle (Floyd's algorithm).
A dummy head node simplifies edge cases when merging or deleting.

Try it yourself

Code editor

class Node:
    def __init__(self, val, next=None):
        self.val, self.next = val, next

def build(values):
    head = None
    for v in reversed(values):
        head = Node(v, head)
    return head

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

def reverse(head):
    prev = None
    while head:
        head.next, prev, head = prev, head, head.next
    return prev

def middle(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
    return slow.val

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:
            return True
    return False

lst = build([1, 2, 3, 4, 5])
print("middle:", middle(lst))
print("reversed:", to_list(reverse(lst)))

loop = build([1, 2, 3])
loop.next.next.next = loop.next          # 3 -> 2 creates a cycle
print("cycle:", has_cycle(loop), has_cycle(build([1, 2])))

Press Run to see the output.

Edit and press Run (or Ctrl/⌘ + Enter). Python runs in your browser — the first run downloads the Python engine and takes a few seconds.

Key points

Access by position is O(n); insert at a known node is O(1).
Reverse with prev/curr pointers.
Fast/slow pointers find the middle and cycles.

Quick check

In Floyd's algorithm, how far does the fast pointer move each step?

1 node 2 nodes Half the list To the end

Practice task

Write merge_sorted(a, b) that merges two sorted linked lists into one sorted list using a dummy head.

Interview corner

Array vs linked list?

Arrays give O(1) index access and are cache-friendly; inserting in the middle is O(n). Linked lists insert/delete at a known node in O(1) but need O(n) to reach a position.

How do you find the k-th node from the end in one pass?

Move a fast pointer k steps ahead, then move both pointers together; when fast reaches the end, slow is k-th from the end.