DSA: Topic 8: Linked Lists

Interview frequency: ⭐⭐⭐⭐☆

Linked Lists are a common DSA interview topic, especially for questions involving pointers, reversing, and detecting cycles.

Since you're learning DSA in Python for exams and interviews, we'll focus on the patterns that actually matter.

1. What is a Linked List?

A linked list is a sequence of nodes.

Each node contains:

1. A value.

2. A reference to the next node.

Singly linked list

Each node points to the next node. The last node points to None.

Unlike an array, linked list nodes do not need to be stored next to each other in memory.

Why does this matter?

In a Python list:

Python

Run

arr = [10, 20, 30]

You can directly access:

Python

Run

arr[1]  # O(1)

In a linked list, to reach the second node, you follow the first node's reference.

Accessing the kth node takes O(n) in the worst case.

2. Create a Linked List in Python

This is the basic implementation you should know for interviews.

Python

Run

class ListNode:

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

Create nodes:

Python

Run

a = ListNode(10)
b = ListNode(20)
c = ListNode(30)

a.next = b
b.next = c

The linked list is:

10 → 20 → 30 → None

The head is:

Python

Run

head = a

3. Traversing a Linked List

Unlike arrays, you cannot use indexes.

Python

Run

def print_list(head):
    curr = head

    while curr:
        print(curr.val)
        curr = curr.next

Output:

10
20
30

Complexity

• Time: O(n)

• Space: O(1)

curr moves through the nodes one by one.

4. Linked List Complexity

Singly linked list

Access by index

O(n)

Search

O(n)

Insert at head

O(1)

Delete at head

O(1)

Insert after known node

O(1)

Delete after known node

O(1)

Insert at tail with tail pointer

O(1)

Important: Inserting or deleting a node is O(1) only when you already have the necessary node/reference. Finding that position may take O(n).

5. Most Important Interview Problem: Reverse Linked List ⭐⭐⭐⭐⭐

LeetCode 206 — Easy, but a must-know.

Problem

Input:

1 → 2 → 3 → 4 → None

Output:

4 → 3 → 2 → 1 → None

The interviewer usually expects an iterative O(1) extra-space solution.

The key idea: Three pointers

Use:

• prev

• curr

• next_node

Initially:

prev = None
curr = head

Step 1

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

Save the next node before reversing.

Step 2

Python

Run

next_node = curr.next
curr.next = prev
prev = curr
curr = next_node

Repeat until curr becomes None.

Python solution

Python

Run

def reverse_list(head):
    prev = None
    curr = head

    while curr:
        next_node = curr.next

        curr.next = prev

        prev = curr
        curr = next_node

    return prev

Dry run

For:

1 → 2 → 3 → None

prev

curr

Start

None

1

1

1

2

2

2 → 1

3

3

3 → 2 → 1

None

Return prev.

Complexity

• Time: O(n)

• Space: O(1)

Critical mistake

Never overwrite curr.next before saving the original next node.

Bad:

Python

Run

curr.next = prev
curr = curr.next

You lose the rest of the list.

6. Fast and Slow Pointers

You learned this pattern earlier. Now we apply it to linked lists.

Use:

• slow moves one step.

• fast moves two steps.

slow → one step
fast → two steps

This pattern solves:

1. Find middle of linked list.

2. Detect cycle.

3. Find the start of a cycle.

4. Find the kth node from the end (using two pointers with a gap).

7. Interview Problem: Middle of Linked List

LeetCode 876 — Easy

Input:

1 → 2 → 3 → 4 → 5

Output:

3

Code

Python

Run

def middle_node(head):
    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    return slow

Why it works

When fast reaches the end, slow has moved half as far.

For an even-length list, this returns the second middle node.

Example:

1 → 2 → 3 → 4

Returns node 3.

Complexity

• Time: O(n)

• Space: O(1)

8. Interview Problem: Linked List Cycle

LeetCode 141 — Easy

Problem

Determine whether a linked list contains a cycle.

Example:

1 → 2 → 3 → 4
    ↑       |
    └───────┘

There is a cycle because the last node points back to an earlier node.

Brute force

Use a set of visited nodes.

Python

Run

def has_cycle_set(head):
    seen = set()
    curr = head

    while curr:
        if curr in seen:
            return True

        seen.add(curr)
        curr = curr.next

    return False

Complexity:

• Time: O(n)

• Space: O(n)

Optimised: Floyd's Cycle Detection

Use slow and fast pointers.

Python

Run

def has_cycle(head):
    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

        if slow is fast:
            return True

    return False

Why is? We want to know whether both variables refer to the exact same node, not whether their values happen to be equal.

Complexity:

• Time: O(n)

• Space: O(1)

9. Interview Problem: Remove Nth Node From End

LeetCode 19 — Medium

Input:

1 → 2 → 3 → 4 → 5

Remove the 2nd node from the end.

Output:

1 → 2 → 3 → 5

Key idea

Use two pointers with a gap of n nodes.

Then move both pointers together.

When fast reaches the end, slow is positioned just before the node to delete.

Python solution

Python

Run

def remove_nth_from_end(head, n):
    dummy = ListNode(0, head)

    slow = dummy
    fast = dummy

    for _ in range(n):
        fast = fast.next

    while fast.next:
        slow = slow.next
        fast = fast.next

    slow.next = slow.next.next

    return dummy.next

Why use a dummy node?

It handles edge cases such as deleting the head.

For example:

1 → 2 → 3

Remove the 1st node from the end:

1 → 2

Without a dummy node, deleting the head needs special handling.

Complexity

• Time: O(n)

• Space: O(1)

10. Linked List Patterns You Must Know

Reverse Linked List

Three pointers: prev, curr, next.

Fast and slow pointers

Middle, cycle detection, nth from end.

Dummy node

Simplifies insertion and deletion at the head.

11. Real Interview Questions

Difficulty

Reverse Linked List

Easy

Middle of the Linked List

Easy

Linked List Cycle

Easy

Merge Two Sorted Lists

Easy

Remove Nth Node From End

Medium

Add Two Numbers

Medium

Reorder List

Medium

Linked List Cycle II

Medium

Copy List with Random Pointer

Medium

Reverse Nodes in k-Group

Hard

12. Exam Cheat Sheet

Think

Reverse a linked list

Three pointers

Find middle

Slow + fast

Detect cycle

Floyd's algorithm

Remove kth from end

Two pointers + dummy

Merge sorted lists

Two pointers

Reverse in groups

Iterative pointer manipulation

Practice question

Try this without looking at the solution:

Reverse a Linked List

Python

Run

def reverse_list(head):
    pass

Input:

1 → 2 → 3 → 4 → None

Expected:

4 → 3 → 2 → 1 → None

Try to solve it using only prev, curr, and next_node.

Next topic: Trees

We'll learn Binary Trees, DFS, BFS, tree height, traversals, and the most common interview problem: Maximum Depth of Binary Tree.