Skip to content
Tutorials Center
My learning

Topics

Lesson 40 of 225 ยท Linked Lists

Linked List Techniques

Core linked list techniques in Python: reverse a list, fast and slow pointers, Floyd cycle detection, merging sorted lists, remove nth from end, dummy nodes.

Almost every linked list interview question is built from a handful of reusable moves. Once you know them well, problems that look new turn out to be a combination of two or three familiar tricks. This lesson teaches the six that matter most: reversing a list, fast and slow pointers (for the middle and for cycles), Floyd's cycle algorithm, merging two sorted lists, removing the nth node from the end, and the humble but powerful dummy node.

Every example uses this node class. We will keep it tiny and add two helpers: one to build a list from a Python list, and one to turn a linked list back into a Python list so we can print it.

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

If you need a refresher on how nodes and pointers work, read linked lists and the singly linked list lesson first.

Technique 1: the dummy node

Many list operations treat the head as a special case. Deleting the head changes what the caller's head variable points to; inserting into an empty list has no previous node. A dummy node (also called a sentinel) is a fake node placed before the real head so that every real node has a predecessor:

TEXT
dummy -> [1] -> [2] -> [3]
  ^
  prev starts here; the answer is dummy.next

Now "delete the first node" and "delete the third node" are the same operation, and you always return dummy.next.

Python Remove all nodes with a value, with and without a dummy

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The build helper uses the dummy trick too: appending to the tail needs no "is the list empty?" branch.

Technique 2: reversing a list

Reversing is the building block of palindromes, reordering and k-group reversal. The idea: walk down the list and flip each next pointer to point backward. You need three names to avoid losing the rest of the list:

TEXT
prev = None        curr = [1] -> [2] -> [3] -> None

step 1: save nxt = curr.next ([2])
        curr.next = prev       (1 -> None)
        prev = curr; curr = nxt

None <- [1]   [2] -> [3] -> None
        ^prev ^curr

Repeat until curr is None; then prev is the new head. That is O(n) time and O(1) extra space.

The recursive version reverses the rest of the list first, then hooks the current node onto the end of the already-reversed part. It is elegant but uses O(n) stack space, so very long lists would hit Python's recursion limit.

Python Reverse iteratively and recursively

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In the recursive version, after the call reverse_recursive(head.next) returns, the node head.next is the tail of the reversed part, so head.next.next = head appends head after it.

Watch out: the most common reversal bug is writing curr.next = prev before saving curr.next. You lose the rest of the list. Always save nxt first.

Technique 3: fast and slow pointers

Move two pointers down the list at different speeds: slow one step at a time and fast two steps. When fast reaches the end, slow is at the middle, because it has traveled half the distance.

TEXT
[1] -> [2] -> [3] -> [4] -> [5] -> None
 s,f
        s       f
               s               f      (f.next is None: stop)
 slow is at 3, the middle

For an even number of nodes, the standard loop while fast and fast.next leaves slow on the second of the two middle nodes. If you need the first, use while fast.next and fast.next.next.

The same pair of pointers detects loops, which brings us to the next technique.

Technique 4: Floyd's cycle detection

A list has a cycle if following next never reaches None. A hash set of visited nodes finds this in O(n) time but O(n) space. Floyd's "tortoise and hare" does it in O(n) time and O(1) space.

The idea: if there is a cycle, the fast pointer eventually enters it and then gains one step per round on the slow pointer. Inside a loop, closing a gap of one step at a time means they must meet.

Finding where the cycle starts

Once they meet, reset one pointer to the head and advance both pointers one step at a time; where they meet again is the first node of the cycle. Why? Let a be the distance from the head to the cycle start, b the distance from the cycle start to the meeting point, and c the cycle length. When they meet, slow has moved a + b and fast has moved 2(a + b). Fast made some whole number of extra laps, so a + b = mยทc, which means a = mยทc - b: walking a more steps from the meeting point brings you exactly to the cycle start (a full number of laps minus b). Starting one pointer at the head and walking a steps reaches the same node.

Python Middle, cycle detection and cycle start

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Because fast jumps two nodes, always check fast and fast.next before reading fast.next.next. Swapping the order of the checks or dropping one of them gives AttributeError: 'NoneType' object has no attribute 'next'.

Technique 5: merging two sorted lists

This is the "merge" step of merge sort, done by relinking nodes rather than copying values. Keep a tail pointer on the result. At each step, attach the smaller front node and advance that list. When one list runs out, attach the rest of the other one in a single move. A dummy node makes the first attachment painless.

Time is O(n + m); extra space is O(1) because we reuse the existing nodes.

Python Merge two sorted lists

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Merge is also how you sort a linked list in O(n log n): split at the middle (technique 3), sort each half recursively, and merge. Arrays lean on quicksort, but linked lists suit merge sort because relinking is cheap and no random access is needed.

Technique 6: remove the nth node from the end

Brute force. Walk once to count the length L, then walk again to node L - n - 1 and unlink the next one. That is two passes, O(L) time.

One pass. Use two pointers separated by a gap of n nodes. Move fast ahead n steps first, then advance both together. When fast reaches the last node, slow is just before the node to delete. Use a dummy node so that deleting the head works without a special case.

TEXT
n = 2, list 1 2 3 4 5   (delete 4)
dummy 1 2 3 4 5
slow=dummy
fast moves 2 ahead -> fast=2
move both until fast.next is None:
  slow=1 fast=3 -> slow=2 fast=4 -> slow=3 fast=5   stop
slow.next is 4: unlink it
Python Remove nth from end in one pass

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both versions are O(L) time and O(1) space; the one-pass version touches each node once instead of twice, which matters when the list is a stream you can only walk through once.

Complexity summary

Technique Time Extra space
Dummy node same as the operation O(1)
Reverse (iterative) O(n) O(1)
Reverse (recursive) O(n) O(n) call stack
Middle (slow/fast) O(n) O(1)
Cycle detect (set) O(n) O(n)
Cycle detect (Floyd) O(n) O(1)
Merge two sorted O(n + m) O(1)
Remove nth from end O(n) O(1)

Common mistakes

  • Losing the rest of the list by overwriting next before saving it.
  • Forgetting None checks on fast.next and fast.next.next.
  • Returning the old head after reversing or after deleting the head. Return prev (reverse) or dummy.next.
  • Leaving a stale pointer. After reversing a segment you must reconnect it at both ends, or a cycle appears.
  • Off-by-one in the gap for remove-nth: starting both pointers at dummy and giving fast exactly n steps is the safe recipe.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why do many linked list algorithms start with a dummy node?

    With a dummy in front, inserting or deleting the first node works exactly like any other position, and you return dummy.next at the end.
  2. 2. In iterative reversal, what is the first thing you must do inside the loop?

    Once curr.next is overwritten, the remaining nodes become unreachable unless you saved a reference first.
  3. 3. For the list 1,2,3,4,5,6, which node does the slow pointer end on with while fast and fast.next?

    slow and fast end on the second middle node, which is 4. With an odd length the middle is unique.
  4. 4. How much extra memory does Floyd's cycle detection use?

    It only keeps two pointers, no matter how long the list is.
  5. 5. To remove the nth node from the end in one pass, how far ahead do you move the fast pointer before moving both?

    A gap of n nodes means that when fast stands on the last node, slow stands just before the node to delete.

Summary

  • A dummy node removes head special cases; return dummy.next.
  • Reversing flips pointers with prev, curr and a saved nxt: O(n) time, O(1) space iteratively.
  • Slow and fast pointers find the middle in one pass and detect cycles in O(1) space (Floyd's algorithm); resetting one pointer to the head finds the cycle start.
  • Merging sorted lists relinks nodes with a tail pointer in O(n + m); it is the heart of merge sort on lists.
  • Remove nth from the end uses a gap of n between two pointers, in one pass.
  • These pieces combine to solve the harder questions in linked list problems.

Next: Linked List Problems