Linked List Operations and Problems

Analogy categoryAnalogies

Introduction

Beyond basic insertion and deletion, linked lists are the foundation of several classic interview and algorithmic problems. These include reversing a list in place, detecting whether a list contains a cycle using Floyd's tortoise and hare algorithm, and finding the middle node in a single pass using two pointers moving at different speeds. Mastering these patterns builds strong intuition for pointer manipulation, which generalizes to many other data structure problems.

🏏

Cricket analogy: Classic linked-list problems mirror cricket puzzles: reversing the batting order in place, detecting if a bowler is stuck repeating the same over sequence (a cycle) using a fast and slow scorer walking the card, and finding the middle over of an innings in one pass using two counters moving at different speeds.

Structure/Syntax

python

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


def build_list(values):
    head = None
    tail = None
    for v in values:
        node = Node(v)
        if head is None:
            head = tail = node
        else:
            tail.next = node
            tail = node
    return head

Explanation

Reversing a list in place uses three pointers (prev, current, next_node) and rewires each node's next pointer to point backward, one node at a time. Floyd's cycle detection algorithm uses two pointers, a slow one advancing one node at a time and a fast one advancing two nodes at a time; if they ever meet, a cycle exists, and if the fast pointer reaches None, there is no cycle. Finding the middle node reuses the same two-pointer technique: when the fast pointer reaches the end, the slow pointer is at the middle, because it has moved half as far.

🏏

Cricket analogy: Reversing the batting order uses three markers (previous batter, current batter, next batter) flipping each link backward one at a time; Floyd's trick sends a slow scorer and a fast scorer through the over sequence, and if they meet there's a repeating loop; finding the middle over reuses this, since when the fast scorer finishes, the slow one is exactly halfway.

Example

python

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


def reverse_list(head):
    prev = None
    current = head
    while current is not None:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    return prev  # new head


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


def find_middle(head):
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
    return slow  # middle node (second middle if even length)


# Build 1 -> 2 -> 3 -> 4 -> 5
n5 = Node(5)
n4 = Node(4)
n4.next = n5
n3 = Node(3); n3.next = n4
n2 = Node(2); n2.next = n3
n1 = Node(1); n1.next = n2

print("Has cycle:", has_cycle(n1))
print("Middle value:", find_middle(n1).value)

reversed_head = reverse_list(n1)
values = []
current = reversed_head
while current is not None:
    values.append(current.value)
    current = current.next
print("Reversed:", values)

Complexity

Reversing a list is O(n) time and O(1) extra space since it only rewires existing pointers. Floyd's cycle detection is O(n) time and O(1) space because the fast pointer catches up to the slow pointer within at most n iterations if a cycle exists, avoiding the O(n) extra space that a hash-set-based approach would need. Finding the middle node with the two-pointer technique is also O(n) time and O(1) space, compared to O(n) time and O(1) space for a two-pass approach that first counts length then walks to n/2 — the one-pass two-pointer method is preferred for its single traversal.

🏏

Cricket analogy: Reversing the innings order costs O(n) time and O(1) space since only the links are rewired; Floyd's cycle check on the over sequence is also O(n) time and O(1) space, cheaper than a hash-set of past overs; finding the middle over in one pass is O(n) time and O(1) space, preferred over a two-pass count-then-walk approach.

Key Takeaways

Reversing a linked list in place uses three pointers (prev, current, next_node) and runs in O(n) time, O(1) space.
Floyd's cycle detection algorithm (tortoise and hare) uses slow and fast pointers; if they meet, a cycle exists.
Cycle detection with two pointers avoids the O(n) extra memory a hash-set approach would require.
The two-pointer technique also finds the middle node in one pass: when fast reaches the end, slow is at the middle.
These pointer-manipulation patterns generalize to many other linked list problems, such as detecting the start of a cycle or checking for palindromes.

Practice what you learned

1. In the in-place reversal algorithm, what does the 'prev' pointer represent at the end of the loop?

2. In Floyd's cycle detection algorithm, how fast does the 'fast' pointer move relative to the 'slow' pointer?

3. What is the space complexity of Floyd's cycle detection algorithm compared to a hash-set-based approach?

4. When the fast pointer reaches the end of the list in the find_middle function, where is the slow pointer?

Was this page helpful?

Circular Linked Lists

Topics covered

#Python#DataStructuresStudyNotes#DataStructures#LinkedListOperationsAndProblems#Linked#List#Operations#Problems#StudyNotes#SkillVeris