Data Structures•Last Updated : 09 Oct 2026

~35 min read

Linked Lists & Pointer Nodes

Master non-contiguous heap allocation, node pointer management, sentinel dummy heads, O(1) in-place list reversals, and Floyd's Tortoise and Hare cycle finding.

Node Architecture & Heap Pointers

A linked list is a recursive, dynamic data structure where each node stores Data and one or more Pointers (References) to adjacent nodes in heap memory. Unlike arrays, nodes are not stored contiguously, allowing instant O(1) insertions and deletions once the target pointer is known.

Singly Linked List:Each node has val and next. Traversal is strictly forward.
Doubly Linked List:Each node has val, next, and prev, enabling bidirectional traversal and true O(1) node removals (used in LRU Cache).
Dummy (Sentinel) Node Pattern:Placing a dummy node before head (dummy.next = head) eliminates edge case checks when deleting or modifying the head node.

In-Place 3-Pointer Reversal: Maintain prev = None, curr = head, and next_temp = None. In each iteration: next_temp = curr.next; curr.next = prev; prev = curr; curr = next_temp.
Floyd's Cycle Detection (Tortoise and Hare): Initialize slow = head and fast = head. Advance slow by 1 step and fast by 2 steps. If a cycle exists, they must meet at a node inside the loop.
Finding the Cycle Entry Point: When slow and fast meet, reset slow = head while keeping fast at the collision point. Advance both by 1 step simultaneously; the node where they meet is the exact cycle entry.

Definition: Floyd's Cycle-Finding Algorithm

A pointer algorithm that uses two pointers moving at different speeds (1x and 2x) to detect loops in linear data structures in O(N) time and O(1) space.

Cycle Entry Mathematical Proof

2 × (L + d) = L + kC + d ==> L = kC - d

Variable Definitions & Term Breakdown:

LDistance from head to the cycle start node

CCircumference / total length of the cycle

dDistance from cycle start to the collision point

kC - dDistance remaining in cycle to reach the entry again

Singly vs Doubly Linked List Benchmark

Property	Singly Linked List	Doubly Linked List	Dynamic Array (Vector)
Node Memory Overhead	1 Pointer (8 bytes)	2 Pointers (16 bytes)	Zero Overhead
Prepend (Head Insert)	O(1)	O(1)	O(N) Shift
Append (with Tail)	O(1)	O(1)	O(1) Amortized
Delete Known Node	O(N) (needs prev)	O(1) (has prev)Optimal	O(N) Shift

Comparison of pointer overhead and mutation speed

Tip

Whenever a problem asks you to remove, reorder, or partition linked list nodes, ALWAYS create a dummy sentinel node `dummy = ListNode(0, head)`. It prevents edge case bugs when mutating the first element.

PythonIn-Place Linked List Reversal Sandbox

1class ListNode:
2    def __init__(self, val=0, next=None):
3        self.val = val
4        self.next = next
5 
6def reverse_list(head: ListNode) -> ListNode:
7    prev = None
8    curr = head
9    while curr:
10        next_temp = curr.next
11        curr.next = prev
12        prev = curr
13        curr = next_temp
14    return prev
15 
16# Helper to build and print list
17def print_list(node):
18    vals = []
19    while node:
20        vals.append(str(node.val))
21        node = node.next
22    return ' -> '.join(vals) + ' -> None'
23 
24head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
25print('Original List:', print_list(head))
26reversed_head = reverse_list(head)
27print('Reversed List:', print_list(reversed_head))

Output

Original List: 1 -> 2 -> 3 -> 4 -> 5 -> None
Reversed List: 5 -> 4 -> 3 -> 2 -> 1 -> None

C++C++ Linked List Cycle Entry Detection

1struct ListNode {
2    int val;
3    ListNode *next;
4    ListNode(int x) : val(x), next(nullptr) {}
5};
6 
7ListNode *detectCycle(ListNode *head) {
8    if (!head || !head->next) return nullptr;
9    ListNode *slow = head, *fast = head;
10    while (fast && fast->next) {
11        slow = slow->next;
12        fast = fast->next->next;
13        if (slow == fast) {
14            ListNode *entry = head;
15            while (entry != slow) {
16                entry = entry->next;
17                slow = slow->next;
18            }
19            return entry;
20        }
21    }
22    return nullptr;
23}

Output

[Returns pointer to cycle entry node or nullptr]

Quick Syntax & Reference Sheet

Concept / Rule	Syntax / Usage
Dummy Head	`dummy = ListNode(0, head); curr = dummy`
Reverse List	`prev = None; while curr: nxt = curr.next; curr.next = prev; prev = curr; curr = nxt`
Cycle Check	`slow = head, fast = head; while fast and fast.next: slow = slow.next, fast = fast.next.next`

Common Pitfalls & Developer Mistakes

✕ Mistake 1:

Losing reference to the next node before modifying curr.next

Why it happens: Assigning `curr.next = prev` before saving `curr.next` causes the rest of the list to be lost forever in memory.

Correction: Always save `next_temp = curr.next` BEFORE overwriting `curr.next`.

# Correct:
next_temp = curr.next
curr.next = prev
prev = curr
curr = next_temp

Frequently Asked Questions

Can we reverse a singly linked list in O(1) space recursively?

No. Recursive reversal requires O(N) auxiliary space on the call stack. Iterative 3-pointer reversal is required for true O(1) auxiliary space.

Hands-On Practice Problems

Practice Coding Challenges (2)Solve in Cloud IDE

[Easy]Reverse Linked List

[Medium]Linked List Cycle Entry

Next: Stacks, Queues & Monotonic Sequences →

Article Tags:#Linked Lists#Pointers#Floyd Cycle#Sentinel Nodes#Reversals

Previous TopicArrays & Contiguous Memory

Next TopicStacks, Queues & Monotonic Sequences

Was this lesson clear and helpful?

Discussion (0)

Loading discussion…

Discuss in community