Skip to content
Laviyx Learn

Try

DSA course menu

Linked List Problems: Reverse, Cycle Detection, Middle and Merge

Solve classic linked list interview problems in Python: reverse a linked list, find the middle with fast and slow pointers, detect a cycle with Floyd's algorithm, merge two sorted lists and remove the nth node from the end.

Intermediate9 min readUpdated
On this page

Almost every linked list problem is solved with a few patterns: re-pointing nodes as you walk, fast and slow pointers, and a dummy node to simplify the head. All examples below use these helpers:

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

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

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

print(to_list(from_list([1, 2, 3])))
Output
[1, 2, 3]

Reverse a linked list#

Walk the list once, turning each next pointer around. Three variables track the previous node, the current node and the next one (saved before it is overwritten):

Python
def reverse(head):
    prev = None
    current = head
    while current:
        nxt = current.next      # 1. remember the rest
        current.next = prev     # 2. turn this pointer around
        prev = current          # 3. step forward
        current = nxt
    return prev                 # the old tail is the new head

print(to_list(reverse(from_list([1, 2, 3, 4, 5]))))
print(to_list(reverse(None)))
Output
[5, 4, 3, 2, 1]
[]

O(n) time, O(1) space.

Find the middle: fast and slow pointers#

Move slow one step and fast two steps at a time. When fast reaches the end, slow is halfway:

Python
def middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow.value

print(middle(from_list([1, 2, 3, 4, 5])))
print(middle(from_list([1, 2, 3, 4, 5, 6])))
Output
3
4

With an even number of nodes, this returns the second of the two middle nodes.

Detect a cycle: Floyd's algorithm#

If some node points back to an earlier node, walking the list never ends. With fast and slow pointers, the fast one laps the slow one inside the loop, so they meet if and only if there is a cycle:

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

straight = from_list([1, 2, 3, 4])
looped = from_list([1, 2, 3, 4])
looped.next.next.next.next = looped.next      # 4 points back to 2

print(has_cycle(straight), has_cycle(looped))
Output
False True

O(n) time and O(1) space. (A set of visited nodes also works, but uses O(n) memory.)

Merge two sorted lists#

A dummy node in front of the result means we never need a special case for "is the result empty?":

Python
def merge(a, b):
    dummy = tail = Node(None)
    while a and b:
        if a.value <= b.value:
            tail.next, a = a, a.next
        else:
            tail.next, b = b, b.next
        tail = tail.next
    tail.next = a or b          # attach whatever remains
    return dummy.next

print(to_list(merge(from_list([1, 4, 7]), from_list([2, 3, 8, 9]))))
Output
[1, 2, 3, 4, 7, 8, 9]

No new nodes are created; the existing nodes are re-linked.

Remove the nth node from the end#

Move a lead pointer n steps ahead, then move both until lead reaches the end. The trail pointer is then just before the node to remove:

Python
def remove_nth_from_end(head, n):
    dummy = Node(None, head)
    lead = trail = dummy
    for _ in range(n):
        lead = lead.next
    while lead.next:
        lead = lead.next
        trail = trail.next
    trail.next = trail.next.next
    return dummy.next

print(to_list(remove_nth_from_end(from_list([1, 2, 3, 4, 5]), 2)))
print(to_list(remove_nth_from_end(from_list([1]), 1)))
Output
[1, 2, 3, 5]
[]

The dummy node handles removing the head (the second case) without extra code.

Common mistakes#

Practice#

Practice exercise

Write is_palindrome_list(head) that returns True if the linked list's values read the same forwards and backwards, using O(1) extra space.

Show hint

Find the middle with fast and slow pointers, reverse the second half, then compare the first half and the reversed second half node by node.

Show solution
Python
class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

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

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

def is_palindrome_list(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
    second = reverse(slow)
    first = head
    while second:
        if first.value != second.value:
            return False
        first, second = first.next, second.next
    return True

for values in [[1, 2, 2, 1], [1, 2, 3, 2, 1], [1, 2, 3]]:
    print(values, is_palindrome_list(from_list(values)))
Output
[1, 2, 2, 1] True
[1, 2, 3, 2, 1] True
[1, 2, 3] False

The one-line swap head.next, prev, head = prev, head, head.next works because Python evaluates the whole right-hand side before assigning. This version changes the list; reverse the second half again afterwards if the caller needs it intact.

Key takeaway#

Next: last in, first out, in Stacks.

Finished this lesson?

Related lessons

DSASingly Linked Lists in Python: Build One From ScratchLearn singly linked lists: nodes and next pointers, building a LinkedList class in Python with append, prepend, insert, delete and search, and how linked lists compare with arrays.Beginner11 min readDSATwo Pointers Technique (With Python Examples)Learn the two pointers technique: opposite-end pointers on sorted arrays, fast and slow pointers, removing duplicates in place, merging sorted lists and the container with most water problem.Beginner8 min readDSADoubly Linked Lists in Python (With an LRU Cache Example)Learn doubly linked lists: nodes with next and prev pointers, sentinel nodes, O(1) removal of any node, and building an LRU cache with a doubly linked list and a dictionary.Beginner10 min read