Python LinkedList exercises — master linked structures

Python LinkedList exercises are where the node-manipulation patterns become automatic. You’ve seen the theory and built three programs. Now it’s time to solve challenges on your own — accessing an element at position N, removing duplicates and detecting cycles. Each one requires a different traversal strategy.

As always: try to solve it yourself, use the hint if stuck for more than 10 minutes, and compare with the commented solution. Use pythontutor.com to step through your solution and watch the pointers move.

The base class

All exercises extend this LinkedList. Start from here:

class LinkedList:
    class Node:
        def __init__(self, value, next_node=None):
            self.value = value
            self.next_node = next_node

    def __init__(self):
        self.__first = None
        self.__length = 0

    def insert_back(self, value):
        new = self.Node(value)
        if self.__first is None:
            self.__first = new
        else:
            current = self.__first
            while current.next_node is not None:
                current = current.next_node
            current.next_node = new
        self.__length += 1

    def insert_front(self, value):
        self.__first = self.Node(value, self.__first)
        self.__length += 1

    def is_empty(self):
        return self.__first is None

    def __len__(self):
        return self.__length

    def __iter__(self):
        current = self.__first
        while current is not None:
            value = current.value
            current = current.next_node
            yield value

    def __str__(self):
        return ' → '.join(str(v) for v in self) + ' → None'

    def to_list(self):
        return list(self)

---

Python LinkedList Exercises — Basic Level

Exercise 1 — Element at position N (from front and from back)

Add two methods to LinkedList:

• get_at(index) — returns the value at position index (0-based from front). Raises IndexError if out of range.
• get_from_back(n) — returns the value at position n from the back (1-based: get_from_back(1) returns the last element). Raises IndexError if out of range.

get_from_back must use the two-pointer technique — the right pointer starts at position n, then both advance together until the right pointer reaches the end. The left pointer is then at position n from the back.

List: 1 → 2 → 3 → 4 → 5 → None
get_at(0) = 1
get_at(2) = 3
get_at(4) = 5

get_from_back(1) = 5  (last)
get_from_back(2) = 4
get_from_back(3) = 3

Expected output:

List: 1 → 2 → 3 → 4 → 5 → None

get_at(0) = 1
get_at(2) = 3
get_at(4) = 5
get_at(5) → IndexError: Index 5 out of range (length 5)

get_from_back(1) = 5
get_from_back(2) = 4
get_from_back(3) = 3
get_from_back(6) → IndexError: n=6 out of range (length 5)

Two-pointer steps for get_from_back(2):
  right advances 2 steps: right at [3]
  both advance together until right.next is None:
    left=[2] right=[4] → left=[3] right=[5]
  return left.value = 3

💡 Hints:

• get_at: loop for _ in range(index) advancing current = current.next_node
• get_from_back(n) two-pointer:
  1. Advance right pointer n steps from first
  2. Start left at first
  3. Advance both together until right.next_node is None
  4. Return left.value
• Handle edge cases: n=0, n > length, empty list

---

Python LinkedList Exercises —Intermediate Level

Exercise 2 — Remove duplicates

Add a method remove_duplicates() that removes all duplicate values from the list, keeping only the first occurrence of each value. Modifies the list in place.

Before: 1 → 2 → 3 → 2 → 4 → 1 → 5 → 3 → None
After:  1 → 2 → 3 → 4 → 5 → None

Before: 5 → 5 → 5 → 5 → None
After:  5 → None

Before: 1 → 2 → 3 → None  (no duplicates)
After:  1 → 2 → 3 → None

Implement two versions:

• remove_duplicates() — uses a set to track seen values. O(n) time, O(n) space.
• remove_duplicates_no_set() — without auxiliary data structures. O(n²) time, O(1) space.

For the no-set version: for each node, traverse all remaining nodes and remove any that have the same value.

💡 Hints:

• With set: seen = set(). Traverse with previous/current pair. If current.value in seen, skip the node (previous.next_node = current.next_node). Otherwise add to seen and advance previous.
• Without set: outer loop on each current. Inner loop: runner = current.next_node, traversing with runner_prev = current. If runner.value == current.value, remove it.
• Update self.__length when removing nodes.
• The first node is always kept — never check if first.value is a duplicate of itself.

---

Python LinkedList Exercises — Final Challenge

Exercise 3 — Cycle detection

In a standard linked list the last node points to None. But if some node’s next_node is modified to point back to a previous node, the list forms a cycle — traversal would loop forever.

Write a method has_cycle() that detects whether the list contains a cycle without modifying the list.

Use Floyd’s cycle detection algorithm (the tortoise and the hare):

• slow pointer advances 1 step per iteration
• fast pointer advances 2 steps per iteration
• If there’s a cycle, fast will eventually catch up to slow inside the cycle
• If there’s no cycle, fast reaches None

For testing, also write create_cycle(position) — a helper that connects the last node to the node at position (0-based), creating a cycle. This method bypasses the normal interface since cycles are test-only constructs.

List without cycle: 1 → 2 → 3 → 4 → 5 → None
has_cycle() = False

List with cycle at position 2:
1 → 2 → 3 → 4 → 5
          ↑_______↑
has_cycle() = True

Also write cycle_entry() — if there’s a cycle, return the value of the node where the cycle begins. Returns None if no cycle.

💡 Hints:

• Floyd’s algorithm:

 <code> slow = fast = self.__first
  while fast is not None and fast.next_node is not None:
      slow = slow.next_node
      fast = fast.next_node.next_node
      if slow is fast:    # comparing objects, not values
          return True
  return False</code>

• The comparison slow is fast checks that they’re the same object in memory — not that they have the same value (two different nodes could have value 5)
• cycle_entry: after detection, reset one pointer to first and advance both 1 step at a time — they meet at the cycle entry node
• create_cycle(position): traverse to last node and also find node at position, then last.next_node = node_at_position
• Warning: if the list has a cycle, __len__ and __iter__ would loop forever — the normal methods don’t protect against cycles

---

Commented solutions

Solution Exercise 1

def get_at(self, index):
    """Return value at 0-based index from front."""
    if index < 0 or index >= self.__length:
        raise IndexError(
            f'Index {index} out of range (length {self.__length})'
        )
    current = self.__first
    for _ in range(index):
        current = current.next_node
    return current.value


def get_from_back(self, n):
    """
    Return value at position n from the back (1-based).
    Uses two-pointer technique — O(n) single pass.
    """
    if n <= 0 or n > self.__length:
        raise IndexError(
            f'n={n} out of range (length {self.__length})'
        )

    # Step 1: advance right pointer n steps
    right = self.__first
    for _ in range(n):
        right = right.next_node    # right is now n steps ahead of start

    # Step 2: advance both until right.next is None
    left = self.__first
    while right is not None:
        left = left.next_node
        right = right.next_node

    # left is now at position n from the back
    return left.value


# Demo
ll = LinkedList()
for v in [1, 2, 3, 4, 5]:
    ll.insert_back(v)

print(f'List: {ll}\n')

# get_at
for i in [0, 2, 4]:
    print(f'get_at({i}) = {ll.get_at(i)}')

try:
    ll.get_at(5)
except IndexError as e:
    print(f'get_at(5) → IndexError: {e}')

print()

# get_from_back
for n in [1, 2, 3]:
    print(f'get_from_back({n}) = {ll.get_from_back(n)}')

try:
    ll.get_from_back(6)
except IndexError as e:
    print(f'get_from_back(6) → IndexError: {e}')

Solution Exercise 2

def remove_duplicates(self):
    """
    Remove duplicate values using a set.
    O(n) time, O(n) space.
    Keeps first occurrence of each value.
    """
    if self.__first is None:
        return

    seen = set()
    seen.add(self.__first.value)

    previous = self.__first
    current = self.__first.next_node

    while current is not None:
        if current.value in seen:
            # Skip this node — it's a duplicate
            previous.next_node = current.next_node
            self.__length -= 1
        else:
            seen.add(current.value)
            previous = current
        current = current.next_node


def remove_duplicates_no_set(self):
    """
    Remove duplicate values without auxiliary data structures.
    O(n²) time, O(1) space.
    """
    current = self.__first

    while current is not None:
        # Remove all subsequent nodes with same value
        runner_prev = current
        runner = current.next_node

        while runner is not None:
            if runner.value == current.value:
                runner_prev.next_node = runner.next_node
                self.__length -= 1
            else:
                runner_prev = runner
            runner = runner.next_node

        current = current.next_node


# Demo
def make_list(values):
    ll = LinkedList()
    for v in values:
        ll.insert_back(v)
    return ll

test_cases = [
    [1, 2, 3, 2, 4, 1, 5, 3],
    [5, 5, 5, 5],
    [1, 2, 3],
    [1],
    [],
]

print('=== WITH SET ===')
for values in test_cases:
    ll = make_list(values)
    print(f'Before: {ll}')
    ll.remove_duplicates()
    print(f'After:  {ll}')
    print()

print('=== WITHOUT SET ===')
for values in test_cases:
    ll = make_list(values)
    print(f'Before: {ll}')
    ll.remove_duplicates_no_set()
    print(f'After:  {ll}')
    print()

# Verify both produce same result
import random
for _ in range(100):
    values = [random.randint(1, 5) for _ in range(10)]
    ll1 = make_list(values)
    ll2 = make_list(values)
    ll1.remove_duplicates()
    ll2.remove_duplicates_no_set()
    assert ll1.to_list() == ll2.to_list(), f'Mismatch for {values}'
print('✓ Both methods produce identical results on 100 random tests')

Solution Exercise 3

def has_cycle(self):
    """
    Detect if the list contains a cycle.
    Uses Floyd's tortoise and hare algorithm.
    O(n) time, O(1) space.
    """
    slow = self.__first
    fast = self.__first

    while fast is not None and fast.next_node is not None:
        slow = slow.next_node              # 1 step
        fast = fast.next_node.next_node    # 2 steps

        if slow is fast:    # same object — cycle detected
            return True

    return False    # fast reached None — no cycle


def cycle_entry(self):
    """
    If there's a cycle, return the value of the node where it starts.
    Returns None if no cycle.

    Algorithm (after Floyd's detection):
    1. Reset one pointer to first
    2. Advance both 1 step at a time
    3. They meet at cycle entry
    """
    slow = self.__first
    fast = self.__first

    # Phase 1: detect cycle
    while fast is not None and fast.next_node is not None:
        slow = slow.next_node
        fast = fast.next_node.next_node
        if slow is fast:
            break
    else:
        return None    # no cycle

    # Phase 2: find entry point
    # Reset one pointer to first, other stays at meeting point
    slow = self.__first
    while slow is not fast:
        slow = slow.next_node
        fast = fast.next_node

    return slow.value    # meeting point is the cycle entry


def create_cycle(self, position):
    """
    TEST HELPER: Create a cycle by connecting last node to node at position.
    WARNING: After calling this, normal iteration methods will loop forever.
    """
    if self.__first is None:
        return

    # Find node at position
    target = self.__first
    for _ in range(position):
        if target is None:
            raise IndexError(f'Position {position} out of range')
        target = target.next_node

    if target is None:
        raise IndexError(f'Position {position} out of range')

    # Find last node and connect to target
    last = self.__first
    while last.next_node is not None:
        last = last.next_node

    last.next_node = target    # create the cycle


# Demo
# Test without cycle
ll = LinkedList()
for v in [1, 2, 3, 4, 5]:
    ll.insert_back(v)

print(f'Normal list: {ll}')
print(f'has_cycle() = {ll.has_cycle()}')
print(f'cycle_entry() = {ll.cycle_entry()}')

# Test with cycle at position 2 (node value=3)
ll2 = LinkedList()
for v in [1, 2, 3, 4, 5]:
    ll2.insert_back(v)

ll2.create_cycle(2)    # last (5) → node at position 2 (value=3)
print(f'\nList with cycle at position 2 (5→3):')
print(f'has_cycle() = {ll2.has_cycle()}')
print(f'cycle_entry() = {ll2.cycle_entry()}')

# Test with cycle at position 0 (full cycle: last → first)
ll3 = LinkedList()
for v in [1, 2, 3]:
    ll3.insert_back(v)

ll3.create_cycle(0)    # last (3) → first (1) — full cycle
print(f'\nList with full cycle (3→1):')
print(f'has_cycle() = {ll3.has_cycle()}')
print(f'cycle_entry() = {ll3.cycle_entry()}')

# Single node no cycle
ll4 = LinkedList()
ll4.insert_back(42)
print(f'\nSingle node: has_cycle() = {ll4.has_cycle()}')

# Single node self-cycle
ll5 = LinkedList()
ll5.insert_back(42)
ll5.create_cycle(0)
print(f'Single node self-cycle: has_cycle() = {ll5.has_cycle()}')

---

Visualise with Python Tutor

Copy this code into pythontutor.com and step through it:

class Node:
    def __init__(self, value, next_node=None):
        self.value = value
        self.next_node = next_node

# List: 1 → 2 → 3 → 4 → 5 → None
nodes = [Node(i) for i in range(1, 6)]
for i in range(4):
    nodes[i].next_node = nodes[i+1]
first = nodes[0]

# get_from_back(2) — two-pointer
n = 2
right = first
for _ in range(n):
    right = right.next_node    # right advances n steps

left = first
while right is not None:
    left = left.next_node
    right = right.next_node

print(f'get_from_back({n}) = {left.value}')    # → 4

# has_cycle — Floyd's algorithm (no cycle here)
slow = fast = first
found = False
while fast is not None and fast.next_node is not None:
    slow = slow.next_node
    fast = fast.next_node.next_node
    if slow is fast:
        found = True
        break

print(f'has_cycle = {found}')    # → False

Step through the two-pointer technique in get_from_back. After advancing right two steps, right is at node value=3. Then both left (at node 1) and right advance together: left→2, right→4, then left→3, right→5, then left→4, right→None. When right reaches None the loop ends and left is at node 4 — which is indeed 2 positions from the back. The two pointers maintain a constant gap of n nodes between them throughout, so when right exits the list, left is exactly n from the end. Then step through Floyd’s algorithm — notice that slow is fast compares object identity (are they the same node in memory?), not value equality. Two different nodes with value 3 would not satisfy slow is fast.

---

Cheat sheet — Python LinkedList

# ============================================
# CHEAT SHEET — Python LinkedList
# Sergio Learns · sergiolearns.com
# ============================================

# NODE — basic unit
class Node:
    def __init__(self, value, next_node=None):
        self.value = value           # the data
        self.next_node = next_node   # reference to next or None

# LINKED LIST
# first ──► [v1] ──► [v2] ──► [v3] ──► None
# Only stores __first reference — O(1) access to first node

# INSERT AT FRONT — O(1)
self.__first = Node(value, self.__first)

# INSERT AT BACK — O(n)
current = self.__first
while current.next_node is not None:
    current = current.next_node
current.next_node = Node(value)

# TRAVERSE — O(n)
current = self.__first
while current is not None:
    process(current.value)
    current = current.next_node    # always advance at end

# DELETE — O(n) — three cases
# Case 1: delete first
self.__first = self.__first.next_node

# Case 2 & 3: find previous node, then skip
previous = self.__first
current = self.__first.next_node
while current is not None:
    if current.value == target:
        previous.next_node = current.next_node    # skip current
        break
    previous = current
    current = current.next_node

# GET AT INDEX — O(n)
current = self.__first
for _ in range(index):
    current = current.next_node
return current.value

# GET FROM BACK — two-pointer, O(n) single pass
right = self.__first
for _ in range(n):       # advance right n steps
    right = right.next_node
left = self.__first
while right is not None:  # advance both together
    left = left.next_node
    right = right.next_node
return left.value          # left is n from back

# REMOVE DUPLICATES — with set, O(n)
seen = set()
seen.add(self.__first.value)
previous, current = self.__first, self.__first.next_node
while current is not None:
    if current.value in seen:
        previous.next_node = current.next_node   # skip duplicate
    else:
        seen.add(current.value)
        previous = current
    current = current.next_node

# CYCLE DETECTION — Floyd's algorithm, O(n), O(1)
slow = fast = self.__first
while fast is not None and fast.next_node is not None:
    slow = slow.next_node               # 1 step
    fast = fast.next_node.next_node     # 2 steps
    if slow is fast:    # is = same object, not equal value
        return True     # cycle detected
return False

# REVERSE — three-pointer, O(n)
previous = None
current = self.__first
while current is not None:
    next_node = current.next_node    # 1. save next
    current.next_node = previous     # 2. flip arrow
    previous = current               # 3. advance previous
    current = next_node              # 4. advance current
self.__first = previous              # new head

# GOLDEN RULES
# 1. Always save next_node before modifying current.next_node
# 2. Handle empty list (first is None) as special case
# 3. Handle first node deletion as special case
# 4. Use slow is fast for object identity — not ==
# 5. Advance current AFTER processing, BEFORE loop check
# 6. while current.next_node is not None → advance to last node
#    while current is not None → process every node

# COMPLEXITY
# Access by index:   O(n)
# Insert front:      O(1)
# Insert back:       O(n) — O(1) if tail pointer maintained
# Delete:            O(n)
# Search:            O(n)
# Traverse:          O(n)
# Two-pointer tricks: O(n) time, O(1) space

# vs Python list
# List: O(1) index, O(n) insert front, O(1) append
# LinkedList: O(n) index, O(1) insert front, O(n) append