Skip to content
Data Structures & Algorithms

Linked Lists interview questions and answers

55 questions, 40 with code. About 4 h 23 min to read them all.

By TestLab · Updated

Plan for an interview
55 questions

Track what you know and what to revise.

Sign in to track progress

You can open a few full answers without signing in. Sign in to read all

1

What is a linked list in data structures?

A linked list is a linear collection of nodes in which each node stores a value and a reference to another node. Unlike an array, its nodes do not need to occupy contiguous memory, so they are accessed by following links rather than by index.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Idea

Each node normally contains two parts:

  • Data field: stores the value, such as an integer or string.

  • Link field: stores a reference to the next node.

The first node is called the head. The last node points to a termination marker such as None in Python or null in Java.

A conceptual three-node list is:

1 -> 2 -> 3 -> None

Following next from the head allows a traversal to visit 1, 2, and 3 in order.

Node Structure

In a singly linked list, each node stores a value and a next reference:

  • val: the node’s value.

  • next: the following node or None.

In a doubly linked list, each node also stores prev, allowing movement in either direction. This simplifies some deletions and reverse traversal, but each node requires additional memory.

A linked list may also be circular, meaning the final node points back to the head instead of terminating with None.

Common Operations

  • Traversal: Start at the head and repeatedly follow next.

  • Search: Compare each visited node’s value with the target.

  • Insertion: Change links to connect a new node into the list.

  • Deletion: Redirect the predecessor’s next reference to bypass the removed node.

  • Reversal: Change each node’s next reference while preserving the original chain.

For example, inserting 4 after 2 changes:

Before: 1 -> 2 -> 3 -> None
After:  1 -> 2 -> 4 -> 3 -> None

Complexity

For a list containing n nodes:

Operation Best Average Worst Reason
Access by index O(n) O(n) O(n) Nodes must be reached by following links
Access through a known node reference O(1) O(1) O(1) The reference already identifies the node
Search by value O(1) O(n) O(n) The target may be the first node or require a full traversal
Insert after a known node O(1) O(1) O(1) Only a constant number of links change
Delete a node with a known predecessor O(1) O(1) O(1) Only the predecessor’s next reference changes
Find the predecessor before deletion O(n) O(n) O(n) A singly linked list must be traversed
Insert or delete at the head O(1) O(1) O(1) The head reference is updated directly

Space complexity: Storing n nodes requires O(n) space, including the input itself. An iterative operation normally uses O(1) auxiliary space. A recursive traversal uses O(n) auxiliary space because the recursion stack can contain one frame per node.

Linked Lists vs Arrays

Characteristic Linked List Array
Access by index O(n) O(1)
Search by value O(n) O(n)
Insert or delete at a known node O(1) O(n) due to shifting
Memory layout Nodes may be distributed across memory Elements are contiguous
Per-element overhead Additional space for links Little or no per-element link overhead
Random access Not supported Supported
Common use Queues, stacks, adjacency lists, LRU caches Fast indexing, buffering, dense collections

Python’s built-in list is a dynamic array, not a linked list.

Common Pitfalls and Interview Tips

  • Forgetting to update every affected link: Insertions and deletions often require saving the previous or next node before changing references.

  • Removing the head incorrectly: The new head must become the old head’s next; an empty-list case must also be handled.

  • Confusing node references with values: A reference points to a node, while val contains the data.

  • Assuming O(1) deletion everywhere: In a singly linked list, deleting a node generally requires finding its predecessor first.

  • Losing the remainder of a list: Save current.next before changing current.next during reversal.

  • Common follow-up questions: Ask about reversing a list, detecting a cycle with fast and slow pointers, merging sorted lists, removing the nth node from the end, or choosing between a singly and doubly linked list.

2

How do linked lists compare with arrays in performance and use cases?

A linked list stores elements in separate nodes connected by references, while an array stores elements in contiguous memory. Linked lists offer efficient insertion and deletion when the affected node is already known, whereas arrays usually provide faster indexing and better memory locality.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How They Work

An array keeps elements in one contiguous block of memory. Its position is calculated directly from the index, producing constant-time access. In Python, list is a dynamically resized sequence backed by a contiguous internal array.

A linked list divides the sequence into nodes. Each node stores a value and a reference to another node:

Before: 1 -> 2 -> 3 -> None

If node 2 is already available, inserting value 4 after it only changes links:

After: 1 -> 2 -> 4 -> 3 -> None

The equivalent Python list changes from [1, 2, 3] to [1, 2, 4, 3]. The linked-list operation is constant time when the node is known, while the list insertion shifts subsequent elements.

Performance Comparison

Operation Array Linked List Reason
Access by index O(1) O(n) An array calculates the address directly; a list must follow references
Search by value O(n) average and worst case O(n) average and worst case Both scan elements
Insert at a known position O(n) O(n) Finding the position in a linked list requires traversal
Insert after a known node O(n) O(1) An array shifts elements; a linked list changes references
Delete a known node O(n) O(1) An array shifts elements; a linked list reconnects neighboring nodes
Append at the end O(1) amortized O(1) with a tail reference; otherwise O(n) Dynamic arrays resize occasionally; singly linked lists may traverse to the tail
Total storage O(n) O(n) Both store n elements, including the input data

No recursion is required, so neither approach adds recursion-stack space. Linked-list nodes consume additional constant space per node for references, while arrays generally have lower per-element overhead.

Advantages of Linked Lists

  • Efficient local changes: Inserting or deleting after a known node takes O(1) time.

  • Flexible sequence size: Nodes can be allocated independently, avoiding the need to shift elements.

  • Useful pointer-based structures: Linked lists naturally support queues, stacks, hash-table chaining, and adjacency-list representations.

  • Straightforward node merging: Two linked sequences can be joined by changing the final node’s reference.

Disadvantages of Linked Lists

  • Slow random access: Accessing the k-th element takes O(n) because each node must be reached through preceding references.

  • Poor cache locality: Nodes may be scattered in memory, increasing cache misses compared with contiguous arrays.

  • Higher memory overhead: Every node stores both a value and one or more references.

  • More allocation overhead: Creating many nodes can be slower and less memory-efficient than storing references in a dynamic array.

  • Complex implementation: Operations involving previous nodes are difficult in a singly linked list and often require a dummy head or additional traversal.

When to Use Each Structure

Use an array or Python list when indexing, iteration speed, compact storage, and cache performance are important.

Use a linked list when the application frequently inserts or deletes elements while already holding a reference to the relevant node. In practice, Python’s built-in list or collections.deque is usually preferable because they are optimized in C. A custom linked list is mainly valuable for learning pointer manipulation or implementing a specialized data structure.

Common Pitfalls

  • Do not claim linked-list indexing is O(1); only traversal to a known node is O(1).

  • Inserting at an index still takes O(n) because the node must first be located.

  • A singly linked list cannot efficiently remove a node given only that node’s value; the previous node must be found.

  • Clarify whether “array” means a fixed-size array or Python’s dynamically resized list.

  • Mention pointer overhead and cache locality, since these are common interview follow-ups.

3

How do singly and doubly linked lists differ?

The key difference is pointer direction: a singly linked list connects each node only to the next node, while a doubly linked list connects each node to both the previous and next nodes. This makes doubly linked lists easier to traverse backward and delete a known node, but they require more memory and require careful pointer maintenance.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Difference

  • Singly linked list: Each node contains val and next.

  • next points to the following node or None.

  • There is no direct pointer to the previous node.

  • Example: 1 -> 2 -> 3 -> None

  • Doubly linked list: Each node contains val, next, and prev.

  • next points forward and prev points backward.

  • The first node's prev and the last node's next are None.

  • Example: 1 <-> 2 <-> 3 -> None

Operations and Complexity

The following times assume a list of n nodes. Best, average, and worst-case results are identical unless stated otherwise.

Operation Singly linked list Doubly linked list Array
Access by index O(n) O(n) O(1)
Search by value O(1) best, O(n) average/worst O(1) best, O(n) average/worst O(1) best, O(n) average/worst
Insert after a known node O(1) O(1) O(n)
Insert before a known node O(n) (predecessor must be found) O(1) O(n)
Delete a known node O(1) if predecessor known, else O(n) O(1) O(n)
Traverse forward O(n) O(n) O(n)
Traverse backward Not directly supported (O(n) with extra memory) O(n) O(n)
Reverse in place O(n) time, O(1) auxiliary space O(n) time, O(1) auxiliary space O(n) time, O(1) auxiliary space
  • Insertion: In a singly linked list, inserting after a known node is O(1); inserting before a known node requires finding the predecessor (O(n)). In a doubly linked list, both are O(1) because prev is available.

  • Deletion: A doubly linked list can unlink a node directly using prev and next. A singly linked list generally needs the predecessor to update its next pointer.

  • Space: Both use O(n) total space for the nodes, excluding auxiliary space. A doubly linked list has the same Big-O space but a higher constant factor because every node stores an extra reference.

  • Recursion: Recursive traversal uses O(n) recursion-stack space. An iterative traversal uses O(1) auxiliary space. Input storage is not counted in the auxiliary-space figures.

Trade-offs

  • Use a singly linked list when memory usage matters and forward-only traversal is sufficient, such as simple queues or adjacency lists.

  • Use a doubly linked list when backward traversal, constant-time deletion of a known node, or efficient navigation in both directions is important, such as browser history or an LRU cache.

  • Arrays are often faster in practice for indexing because they provide direct O(1) access. Linked lists are more flexible when frequent insertion and deletion occur at known positions.

Common Pitfalls and Interview Tips

  • Updating next without updating the corresponding prev pointer in a doubly linked list.

  • Forgetting that deleting a node from a singly linked list usually requires finding its predecessor.

  • Assuming indexed access is O(1) in a linked list; it is O(n).

  • Being careful with one-based versus zero-based indexing and with off-by-one errors during traversal.

  • Remembering that Python has no fixed-width integer overflow for ordinary int values, but other languages may require checking index and value limits.

  • Deleting nodes mutates the original list. If a problem forbids mutation, copy the nodes first.

  • A common follow-up is cycle detection: use fast and slow pointers with Floyd’s algorithm; after the pointers meet, restarting one pointer from the head and moving both one step at a time finds the cycle’s entry node without a visited set. Also ask whether backward traversal, deletion, or reversal is needed; those requirements often determine which list type is best.

4

How does a linked list allocate memory differently from an array?

A linked list stores each element in a separately allocated node connected through references, whereas an array reserves a contiguous block for its elements or references. Linked-list nodes may therefore be scattered across memory, while array slots are adjacent.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Memory Allocation

  • Array: Uses one contiguous block. A fixed array has a predetermined capacity; a dynamic array may reserve extra capacity so it can grow without copying after every insertion.

  • Linked list: Allocates a node containing the value and a reference to the next node. Each node is a distinct logical object, although an allocator may place several nodes in the same memory pool.

  • Per-element overhead: A linked-list node needs storage for both its value and its link. Consequently, a linked list usually has a larger memory constant than a compact array of primitive values.

  • Python example: A Python 3.12 list stores object references. In CPython 3.12, those references are held in a contiguous, dynamically resized buffer, while the referenced objects may be allocated elsewhere.

Complexity and Array Comparison

The table assumes a singly linked list, a tail reference for linked-list append, and a dynamically resizable array.

Operation Linked List Array Reason
Access by index O(n) O(1) A linked list must follow links, while an array calculates the slot address directly.
Insert after a known node O(1) O(n) Only the links change; array elements must be shifted.
Delete when the predecessor is known O(1) O(n) Updating the predecessor’s link is constant-time; array elements must be shifted.
Find an unsorted value O(n) average and worst case O(n) average and worst case Both require scanning the stored values.
Append at the end O(1) with a tail reference O(1) amortized A node is linked at the tail; a dynamic array occasionally resizes and copies its elements.

For indexed access and unsorted search, the best case is O(1) when the desired element is encountered immediately; the average and worst cases are O(n). Known-position insertion and deletion are O(1) in the best, average, and worst cases. Linked-list append with a tail reference is O(1) in all cases; without a tail reference, locating the tail takes O(n). Dynamic-array append is O(1) in the best case, O(1) amortized per operation over a sequence, and O(n) in the worst case for one append that triggers resizing.

Total storage is O(n) for both structures, including the input; linked-list nodes have additional per-node overhead. Core pointer manipulation uses O(1) auxiliary space, including an iterative traversal’s stack. The input is excluded from auxiliary-space accounting but included in total storage.

Allocation Walkthrough

For the values 1, 2, and 3:

  1. The empty linked list is None.

  2. Allocating a node for 1 produces 1 -> None.

  3. Allocating and linking a node for 2 produces 1 -> 2 -> None.

  4. Before appending 3, the state is 1 -> 2 -> None.

  5. Allocating and linking the final node produces 1 -> 2 -> 3 -> None.

The corresponding dynamic-array states are [], [1], [1, 2], and [1, 2, 3]. Its logical length grows in those steps, although its allocated capacity may temporarily exceed its length.

Practical Guidance

  • Choose an array when random access, cache-friendly scanning, or low per-element overhead matters most.

  • Choose a linked list when nodes are frequently inserted or deleted after a known predecessor and sequential traversal is acceptable.

  • Use a dummy head: A sentinel node provides a stable link before the first element, simplifying insertion at the head and other empty-list edge cases. It does not remove the general need to locate an arbitrary node’s predecessor for deletion.

  • Prefer Python’s built-in list in application code: It is optimized, contiguous at the reference-buffer level, and usually faster than a custom ListNode implementation. A custom linked-list implementation is more useful for learning pointer algorithms or when an external library already requires that representation.

Common Pitfalls and Interview Tips

  • Do not assume linked lists use less total memory; their node and reference overhead often makes them larger.

  • Treat insertion and deletion as O(1) only when the required location or predecessor is already available.

  • Distinguish dynamic-array amortized O(1) append from the O(n) worst case for one resize.

  • A reference is a logical link, not necessarily a physical memory address.

  • When implementing operations, guard against off-by-one errors, accidental input mutation, and integer overflow in fixed-width languages.

  • Typical follow-up questions include reversing a list, detecting a cycle with Floyd’s algorithm, and merging sorted lists. Cycle-detection solutions must track visited state or use the required fast-and-slow pointer pattern.

5

What operations are supported by linked lists?

A linked list stores elements in connected nodes, where each node contains a value and a reference to the next node. Standard operations include traversal, search, insertion, deletion, updating, and reversal.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Linked Lists Work

Each node stores:

  • val: The element’s value.

  • next: A reference to the following node.

  • prev: An optional backward reference, used in doubly linked lists.

A dummy sentinel head represents the start of the list. Its value is not part of the logical list, and head.next points to the first real node. This simplifies insertion and deletion because the first element is then handled like every other element.

For example:

  • Before insertion: 1 -> 2 -> 3 -> None

  • After inserting 4 after 2: 1 -> 2 -> 4 -> 3 -> None

  • After reversal: 3 -> 2 -> 1 -> None

Core Operations and Complexity

The following complexities assume an iterative implementation. Auxiliary space excludes the input list itself.

Operation Best Average Worst Auxiliary space
Traverse O(n) O(n) O(n) O(1)
Search by value O(1) O(n) O(n) O(1)
Access by index O(1) O(n) O(n) O(1)
Insert after a known node O(1) O(1) O(1) O(1)
Delete a known node O(1) O(1) O(1) O(1)
Insert or delete at the head O(1) O(1) O(1) O(1)
Append without a maintained tail O(n) O(n) O(n) O(1)
Reverse O(n) O(n) O(n) O(1)
Calculate length O(n) O(n) O(n) O(1)
  • Why O(n) for search? Each node may require inspection, and the target might be last.

  • Why O(1) for known-node changes? Linking or unlinking a node requires changing only a constant number of references.

  • Recursion stack: Recursive traversal or reversal uses O(n) stack space; an iterative implementation uses O(1).

Linked Lists Compared with Arrays

Operation Linked list Array
Access by index O(n) O(1)
Insert or delete at a known node O(1) O(n)
Insert or delete at the head O(1) O(n)
Memory per element Includes pointer overhead Usually more compact
Cache locality Usually weaker Usually better

Linked lists are useful when frequent insertion and deletion are required. Arrays are usually better when random indexing and cache-friendly iteration are priorities.

Code Example

from __future__ import annotations

from dataclasses import dataclass


@dataclass
class ListNode:
    val: int
    next: ListNode | None = None
    prev: ListNode | None = None


def insert_after(node: ListNode, value: int) -> ListNode:
    """Insert a new node immediately after node."""
    new_node = ListNode(value, next=node.next, prev=node)
    if node.next is not None:
        node.next.prev = new_node
    node.next = new_node
    return new_node


def delete_after(node: ListNode) -> ListNode:
    """Delete and return the node immediately after node."""
    removed = node.next
    if removed is None:
        raise ValueError("There is no node to delete")

    following = removed.next
    node.next = following
    if following is not None:
        following.prev = node

    removed.next = None
    removed.prev = None
    return removed


def cycle_entry(head: ListNode) -> ListNode | None:
    """Return the cycle's entry node using Floyd's algorithm."""
    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:
            slow = head
            while slow is not fast:
                slow = slow.next
                fast = fast.next
            return slow

    return None


def find(head: ListNode, target: int) -> ListNode | None:
    """Find the first matching value, including in a cyclic list."""
    entry = cycle_entry(head)
    current = head.next

    while current is not None and current is not entry:
        if current.val == target:
            return current
        current = current.next

    if entry is None:
        return None

    current = entry
    while True:
        if current is not head and current.val == target:
            return current
        current = current.next
        if current is entry:
            return None


def reverse(head: ListNode) -> None:
    """Reverse a finite list while retaining its sentinel head."""
    if cycle_entry(head) is not None:
        raise ValueError("Cannot reverse a cyclic list")

    previous = None
    current = head.next

    while current is not None:
        next_node = current.next
        current.next = previous
        current.prev = next_node
        previous = current
        current = next_node

    head.next = previous
    if previous is not None:
        previous.prev = head


def to_list(head: ListNode) -> list[int]:
    """Convert a finite linked list to a Python list."""
    if cycle_entry(head) is not None:
        raise ValueError("Cannot convert a cyclic list to a finite list")

    values = []
    current = head.next
    while current is not None:
        values.append(current.val)
        current = current.next
    return values


if __name__ == "__main__":
    head = ListNode(0)  # Dummy sentinel
    first = ListNode(1)
    head.next = first
    first.prev = head
    first.next = ListNode(2, prev=first)

    insert_after(first, 99)
    print(to_list(head))  # [1, 99, 2]

    delete_after(first)
    print(to_list(head))  # [1, 2]

    reverse(head)
    print(to_list(head))  # [2, 1]

    match = find(head, 2)
    print(match.val if match is not None else None)  # 2

Common Pitfalls

  • Empty list: It contains only the sentinel, so head.next is None.

  • One element: Inserting after the sentinel works normally; deleting the only element restores head.next = None.

  • Duplicates: Search returns the first matching node. To delete a particular duplicate, identify the node by reference rather than value alone.

  • Negative values: They are valid and require no special handling.

  • Cycles: Traversal without cycle detection can loop forever. find uses Floyd’s algorithm, while list-modifying operations reject cyclic lists.

  • Sorted input: It does not change basic operation costs; sortedness matters only for operations such as merging.

  • Disconnected components: A single linked list has no disconnected components; separate lists represent separate components.

  • Common mistake: When deleting a node in a doubly linked list, update both the predecessor’s next and the successor’s prev.

6

Real-life use cases of linked lists

Linked lists are used when frequent insertions and deletions at arbitrary positions are needed, when the size is unknown or changes dynamically, or when memory must be allocated in non-contiguous blocks. They trade O(1) random access for O(1) insertion/deletion at a known node.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

When Linked Lists Outperform Arrays

Operation Linked List Array / Dynamic Array
Access by index O(n) O(1)
Insert/delete at known node O(1) O(n) (shift elements)
Insert/delete at head O(1) O(n)
Memory layout Non-contiguous nodes Contiguous block
Cache locality Poor Excellent
Size flexibility Unlimited (until memory exhausted) Amortized O(1) append, but occasional resize

Real-World Applications

  • Operating system schedulers: Process control blocks (PCBs) are linked in ready, waiting, and blocked queues. The scheduler moves PCBs between lists in O(1) when a process changes state.

  • Browser history: Back/forward navigation is a doubly linked list of visited URLs. Each entry points to the previous and next page, enabling O(1) movement in either direction.

  • Music/video playlists: Tracks are nodes; adding, removing, or reordering songs is O(1) at a known position. Shuffle and repeat modes are pointer manipulations.

  • Undo/redo stacks: Each editor state is a node. Undo moves a pointer backward; redo moves it forward. Branching undo histories (e.g., after new edits post-undo) are naturally modeled with linked structures.

  • Memory allocators: Free lists track available memory blocks. Allocators splice blocks in and out of size-segregated linked lists in O(1).

  • Hash table chaining: Colliding keys are stored in a linked list (or tree) at each bucket. Insertion and deletion at the bucket head are O(1).

  • Graph adjacency lists: Each vertex holds a linked list of neighbors. Adding/removing edges is O(1) without resizing arrays.

  • LRU caches: A doubly linked list orders entries by recency; a hash map gives O(1) node access. Moving a node to the front on access is O(1).

  • Polynomial manipulation: Sparse polynomials store only non-zero terms as nodes (coefficient, exponent, next). Addition and multiplication traverse and merge lists.

  • File systems: Directory entries and block allocation tables often use linked structures (e.g., FAT file system’s cluster chain).

Key Pointer Patterns in Practice

  • Dummy/sentinel head: Eliminates special-case code for empty lists or head modifications. The dummy node always exists; real data starts at dummy.next.

  • Fast/slow pointers: Find middle (slow moves 1, fast moves 2), detect cycles (Floyd’s algorithm), or find k-th from end.

  • Reversal (prev/curr/next): Iteratively reverse pointers in O(n) time, O(1) space.

  • Two-pointer gap: Maintain a fixed distance (e.g., n nodes) to remove the n-th node from the end in one pass.

  • Merge two sorted lists: Compare heads, splice the smaller node, advance that list’s pointer.

List State Visualization

Before reversal: 1 -> 2 -> 3 -> None
After reversal: 3 -> 2 -> 1 -> None
Insert 4 after 2: 1 -> 2 -> 4 -> 3 -> None (O(1) given node 2)
Remove 2: 1 -> 4 -> 3 -> None (O(1) given node 1, or O(n) to find predecessor in singly linked)

Common Pitfalls

  • Forgetting the dummy head: Leads to repetitive if head is None checks and bugs when modifying the first node.

  • Losing the rest of the list: During insertion/deletion, always save curr.next before overwriting curr.next.

  • Cycle creation: Accidentally pointing a node to an earlier node creates an infinite loop on traversal.

  • Memory leaks (non-GC languages): Failing to free removed nodes; in Python, dereference them so the GC can collect.

  • Assuming O(1) access: Linked lists are not random-access; indexing is O(n). Use arrays or deque when index access is frequent.

  • Interview follow-ups: “Implement LRU cache,” “Detect and remove cycle,” “Merge k sorted lists,” “Copy list with random pointer,” “Reorder list (L0→Ln→L1→Ln-1…).”

7

Which workloads benefit from a circular linked list?

A circular linked list is useful when processing naturally continues from the last element back to the first. It supports cyclic workloads such as round-robin scheduling, playlists, periodic timers, game turns, and fixed-size memory pools without repeatedly rebuilding the ordering.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

When It Is Useful

Circular linked lists work well when the data has a repeating or continuously rotating order:

  • Round-robin processing: Select one task at a time and continue from the next task.

  • CPU time slicing: Model processes receiving fixed execution turns.

  • Playlists and game turns: Move through participants repeatedly.

  • Periodic task scheduling: Revisit recurring maintenance or monitoring tasks.

  • Memory pools: Cycle through reusable blocks of memory.

  • State machines: Move from each state back to the first after the final state.

The circular-buffer concept is similar, but a circular buffer is usually array-backed. A circular linked list is preferable when nodes need to be inserted, removed, or connected dynamically.

How It Works

In a singly circular linked list, the final node points back to the first:

1 -> 2 -> 3 -> 1

A dummy sentinel head is commonly added so traversal has an explicit stopping point:

sentinel -> 1 -> 2 -> 3 -> sentinel

The sentinel simplifies empty-list handling and avoids checking several separate None conditions. Traversal starts at sentinel.next and stops when it reaches the sentinel again.

For example, advancing the current position once changes:

Before: sentinel -> 1* -> 2 -> 3 -> sentinel
After:  sentinel -> 1 -> 2* -> 3 -> sentinel

The links are unchanged; only the current pointer moves.

Complexity

Operation Best Average Worst Reason
Access a known node O(1) O(1) O(1) Follows directly through next
Search by value O(1) O(n) O(n) Must inspect nodes sequentially
Insert after a known node O(1) O(1) O(1) Changes a constant number of links
Delete a known node O(1) O(1) O(1) Redirects the previous node
Append with a tracked tail O(1) O(1) O(1) Links the old tail to the new node
Move to the next item O(1) O(1) O(1) Reads one next pointer
Traverse all n items O(n) O(n) O(n) Visits every item once

For n stored nodes, total space is O(n), including the nodes themselves. Additional auxiliary space is O(1) when a tail or current pointer is maintained; there is no recursion stack. Whether the original input is counted depends on whether the implementation reuses its nodes.

Comparison With Arrays

Operation Circular linked list Array
Access by index O(n) O(1)
Access a known node or position O(1) O(1)
Insert or delete at a known node/position O(1) O(n)
Move to the next element O(1) O(1)
Extra structural space One node per element O(1) auxiliary

Linked lists avoid shifting elements, but they provide worse random access and usually consume more memory because every element stores a pointer.

Code Example

from typing import Generic, TypeVar

T = TypeVar("T")


class ListNode(Generic[T]):
    def __init__(self, val: T) -> None:
        self.val = val
        self.next: ListNode[T] | None = None


def round_robin(tasks: list[str], rounds: int) -> list[str]:
    """Return task selections produced by circular round-robin processing."""
    if not tasks or rounds <= 0:
        return []

    sentinel = ListNode("__sentinel__")
    first = ListNode(tasks[0])
    sentinel.next = first

    tail = first
    for task in tasks[1:]:
        node = ListNode(task)
        tail.next = node
        tail = node

    # Close the list through the sentinel.
    tail.next = sentinel

    current = sentinel.next
    selections: list[str] = []

    for _ in range(rounds):
        if current is None or current is sentinel:
            current = sentinel.next

        assert current is not None
        selections.append(current.val)
        current = current.next

    return selections


print(round_robin(["A", "B", "C"], 5))
# Expected output: ['A', 'B', 'C', 'A', 'B']

Setup takes O(n) time. Each round takes O(1) time, so the function takes O(n + rounds) time. It uses O(n + rounds) space including the nodes and returned selections, with no recursion stack.

Common Pitfalls

  • Infinite traversal: Without a sentinel, node count, or comparison with the starting node, traversal may never terminate.

  • Confusing nodes with values: Use identity comparisons such as current is sentinel, not current == sentinel.

  • Ignoring special cases: Empty input and nonpositive round counts should return an empty result; one task repeats, and duplicate task names remain separate nodes.

  • Choosing the wrong structure: Use an array-backed circular buffer when fixed capacity and low overhead matter more than dynamic node operations.

  • Following up: Interviewers commonly ask about adding/removing nodes, detecting mistakes in termination, reversing a circular list, and choosing between a circular linked list and collections.deque.

8

When is a doubly linked list more efficient than a singly linked list?

A doubly linked list is more efficient when an operation requires access to both the next and previous nodes. Its extra prev pointer enables constant-time backward traversal and deletion of a known node, whereas a singly linked list generally needs an O(n) search for the predecessor.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

When Doubly Linked Lists Help

  • Deleting a known node: Given a reference to the node, a doubly linked list can unlink it in O(1) time by updating both neighboring nodes. A singly linked list must find the preceding node, normally taking O(n) time.

  • Backward traversal: Following node.prev takes O(1) per step. A singly linked list cannot traverse backward without reversing or rebuilding the list or using additional storage.

  • Deleting the tail: If the tail node is available, deletion is O(1) because its predecessor is accessible through prev. Deleting the tail of a singly linked list normally takes O(n).

  • Moving nodes or maintaining adjacency: Both neighbors can be accessed directly, which can simplify operations that reorder elements or maintain links in both directions.

  • Certain editor and cache designs: Features such as undo history, text cursors, and LRU-cache implementations often benefit from moving backward and removing an entry directly.

These benefits apply only when the required node is already known. Access by index and search by value remain O(n) in the worst case in both structures.

Operation Complexity

Let n be the number of elements. Average search and access bounds assume a uniformly random target or position.

Operation Singly linked list Doubly linked list Array
Access by index Best O(1) at index 0; average and worst O(n) Best O(1) at index 0; average and worst O(n) O(1) in all cases
Search by value Best O(1) for a first-node match; average and worst O(n) Best O(1) for a first-node match; average and worst O(n) Best O(1); average and worst O(n)
Insert after a known linked node or at a known array position O(1) in all cases O(1) in all cases Best O(1) when no shifting is needed; average and worst O(n) due to shifting
Delete a known linked node or at a known array index Best O(1) for the head; average and worst O(n) without the predecessor O(1) in all cases Best O(1) when no shifting is needed; average and worst O(n) due to shifting
Move to the predecessor from a known node or index Best O(1); average and worst O(n) O(1) in all cases O(1) in all cases
Delete the tail O(n) to find the predecessor O(1) if the tail node is known O(1) for a known final slot, excluding resizing
Full forward traversal O(n) in all cases O(n) in all cases O(n) in all cases

The reasons follow from pointer availability: each traversal step is O(1), but reaching an arbitrary position can require visiting O(n) nodes. Moving or removing array elements can also require O(n) shifts.

Example

For a doubly linked list, the state before deleting node 2 is:

  • Before: 1 <-> 2 <-> 3 <-> None

  • After: 1 <-> 3 <-> None

The operation updates 1.next and 3.prev. For a singly linked list:

  • Before: 1 -> 2 -> 3 -> None

  • After: 1 -> 3 -> None

Deleting 2 requires finding and updating its predecessor, so it takes O(n) time unless the predecessor is already available.

Space Trade-Off

  • Auxiliary space: O(1) for an iterative traversal or direct node operation, excluding the input.

  • Recursion stack: O(1) for iterative implementations; a recursive traversal uses O(n) stack space.

  • Input storage: O(n) for either linked-list type, including the nodes; a doubly linked list additionally stores one prev pointer per node.

  • Pointer maintenance: Insertion and deletion update more links, introducing a small constant-factor cost.

The extra pointer therefore exchanges higher per-node memory usage and slightly more pointer maintenance for O(1) predecessor access and backward movement.

Common Pitfalls

  • “Doubly linked lists are always faster”: They are not. Search, indexing, and full traversal remain O(n) in the worst case, while the extra pointer increases memory usage.

  • Confusing a known node with a known position: Direct deletion is O(1) only when the node reference is already available. Finding that node by value still costs O(n) in the worst case.

  • Forgetting to maintain all links: Insertion or deletion must update both next and prev references consistently.

  • Ignoring edge cases: Empty, one-element, head-only, and tail-only lists need explicit handling in an implementation.

  • Using a dummy head: A sentinel head simplifies insertion and deletion at the beginning by removing special-case pointer updates, at the cost of one additional node.

Interview Tips

When discussing efficiency, specify whether the node reference is known. The strongest justification is usually O(1) deletion of a known node or O(1) backward movement, not faster searching. Also mention the memory cost of storing prev and the need to keep both sets of links consistent.

9

When is a linked list better than a dynamic array?

A linked list is often better when insertions and deletions occur at the ends or when references to the relevant nodes are available, because it avoids shifting elements. This advantage comes with slower indexed access, additional pointer overhead, and generally poorer cache locality.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Suitable Scenarios

A common example is implementing a FIFO queue with frequent operations at both ends:

  • Enqueue: add an element at the rear.

  • Dequeue: remove an element from the front.

With a linked list that tracks its head and tail, both operations take O(1) time. A dynamic array may append in amortized O(1) time, but removing its first element requires shifting the remaining elements, taking O(n) time.

A doubly linked list is especially useful when a program holds a reference to the node it wants to remove. For example, an LRU cache can use a doubly linked list for ordering and a hash map to locate an entry’s node in O(1) average time.

Operation Walkthrough

Consider a FIFO queue containing 10, 20, and 30:

Before removing the first element:

dummy -> 10 -> 20 -> 30 -> None

After removing 10:

dummy -> 20 -> 30 -> None

A dummy sentinel head simplifies the implementation:

  • The dummy node always exists, so the queue never requires replacing its head.

  • Removing the first real element is handled like removing any other node.

  • When the final element is removed, the tail is reset to the dummy head.

  • Empty-list checks become straightforward.

The values themselves do not affect pointer operations, so duplicates and negative numbers work normally.

Complexity Comparison

The entries show best, average, and worst-case time where they differ.

Operation Linked list Dynamic array Reason
Access by index O(n) / O(n) / O(n) O(1) / O(1) / O(1) Linked lists must be traversed; arrays use direct indexing.
Search for an unsorted value O(1) / O(n) / O(n) O(1) / O(n) / O(n) The first element can match immediately; later matches and unsuccessful searches are linear.
Insert after a known node O(1) / O(1) / O(1) O(n) / O(n) / O(n) A linked list changes one pointer; an array shifts elements.
Remove a known node O(1) for a doubly linked list; O(1) with a known predecessor or O(n) without one for a singly linked list O(n) / O(n) / O(n) Linked-list pointer updates are constant-time when the necessary references are available; arrays shift elements.
Remove the front element O(1) / O(1) / O(1) O(n) / O(n) / O(n) A linked list advances its head; an array shifts its contents.
Append O(1) with a maintained tail; otherwise O(n) Best O(1), average O(1), worst O(n), amortized O(1) A dynamic array may resize and copy all elements.

For either structure:

  • Total stored space: O(n), counting the stored input elements. A linked list also stores node references, while a dynamic array may retain unused capacity.

  • Auxiliary space: O(1) for linked-list pointer updates and array access, search, or non-resizing operations. A dynamic-array append that allocates a new backing array may temporarily use O(n) additional space depending on the implementation.

  • Recursion stack: O(1) for iterative implementations; no recursive calls are required.

Advantages and Limitations

  • Advantages: Constant-time local insertion and deletion, efficient front and rear operations, and no element shifting.

  • Limitations: Linear-time indexed access, extra pointer overhead, and generally worse cache locality than contiguous arrays.

  • Practical consideration: In Python, use collections.deque for a FIFO queue rather than implementing one with a linked list. A custom linked list is more appropriate when the application specifically needs node-level operations or integration with another structure.

Interview Tips

  • Choose a linked list when local modifications dominate and the necessary node references are available.

  • Choose a dynamic array when random indexing, compact storage, or cache-friendly traversal dominates.

  • Distinguish singly and doubly linked lists: a known node can be removed in O(1) in a doubly linked list, while a singly linked list also needs the predecessor.

  • Always handle the empty-list case and reset the tail when the last node is removed.

  • A common follow-up asks why a dynamic-array append is amortized O(1) even though an individual resize can take O(n).

10

How do array-based and linked-list stack implementations compare?

An array-based stack stores elements in contiguous memory and uses the end of the array as its top, while a linked-list stack stores each element in a node and uses the head as its top. Linked-list stacks provide consistently constant-time insertions and removals, whereas dynamically sized array stacks have amortized constant-time pushes but occasionally pay an O(n) resizing cost.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Differences

Characteristic Array-based stack Linked-list stack
Top element Last array element First node after the sentinel head
Push Amortized O(1); worst O(n) during resizing O(1) in all cases
Pop O(1) in all cases O(1) in all cases
Peek O(1) in all cases O(1) in all cases
Memory layout Contiguous Scattered node allocations
Memory overhead Lower per element Additional next pointer per node
Size management Grows, shrinks, or reaches a fixed capacity Grows one node at a time
Common use Performance-sensitive stacks with predictable size Frequently changing stacks needing fast growth

For a fixed-capacity array, push is also O(1) while capacity remains. On overflow, the implementation either raises an error or resizes the array, which costs O(n).

How the Implementations Work

  • Array-based stack: push appends to the end of the array; pop removes the last element; peek reads the last element.

  • Linked-list stack: push creates a node whose next points to the current top; pop moves the head to the next node.

  • Sentinel head: The linked implementation uses a dummy ListNode whose next points to the actual top. This avoids separate handling for the first real node and simplifies empty-stack checks.

  • No tail traversal: Stack operations happen at the head, so they do not require walking through the list.

Complexity Analysis

For n stored stack elements:

  • Array push: best O(1), amortized O(1), and worst O(n) when the underlying array must resize and copy its elements.

  • Array pop and peek: best, average, and worst O(1) because they access the final array position directly.

  • Linked-list push, pop, and peek: best, average, and worst O(1) because each operation changes or reads only the head node.

  • Array storage: O(n) total space for the stored elements, plus up to O(n) temporary space during a resize.

  • Linked-list storage: O(n) total space for the nodes and their next references.

  • Auxiliary space per operation: O(1) for both implementations. The occupied stack storage is counted, and neither implementation uses a recursion stack.

Common Pitfalls

  • Popping or peeking an empty stack must raise a clear error rather than returning an invalid value.

  • list.pop(0) and list.insert(0, value) are O(n); stack operations should use the end of the array.

  • A fixed-capacity stack must define its overflow behavior explicitly.

  • When stating linked-list insertion complexity, confirm that the insertion node or its predecessor is already known.

  • Common follow-up questions ask about stack implementation using queues, avoiding recursion, and whether deque should be used instead of a custom linked-list stack.

11

How do Linked Lists Compare with Trees?

Linked lists are linear structures suited to sequential traversal and constant-time pointer updates when the affected node is already known. Balanced search trees support O(log n) search and updates, plus efficient ordered-range queries taking O(log n + k) for k results.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Differences

  • Linked list: A linear sequence of nodes, where each node stores a value and one or more links to neighboring nodes.

  • Tree: A hierarchical structure whose nodes have parent and child relationships.

  • Balanced search tree: Maintains height O(log n), guaranteeing efficient search and modification.

  • Unbalanced tree: A skewed tree can have height O(n), making operations as slow as a linked list.

  • Ordering: A sorted linked list supports ordered traversal, but searching still takes O(n) worst-case time. A balanced binary search tree maintains ordering while supporting O(log n) worst-case lookups.

Operation Complexity

Operation Linked List Balanced Search Tree
Access by index O(n) because nodes must be traversed O(n) ordinarily; O(log n) with order-statistic augmentation
Search by key Best O(1); average and worst O(n) Best O(1); average and worst O(log n)
Insert or delete at a known node O(1) for the pointer update O(log n) in standard implementations when balancing or successor lookup is required
Insert or delete by key O(n) to locate the position O(log n)
Access or update by index O(n) to locate the position O(n) ordinarily; O(log n) with order-statistic augmentation
Find minimum or maximum O(1) with the relevant endpoint reference; otherwise O(n) O(log n) ordinarily; O(1) with augmented extrema references
Traverse all elements O(n) O(n)
Ordered range query O(n + k) O(log n + k), where k is the number of results

For an arbitrary tree, searching takes O(h), where h is its height. A balanced tree has h = O(log n), while a skewed tree can have h = O(n).

For n stored elements, both structures require O(n) total space, so the input itself is counted. Iterative traversal of a linked list uses O(1) auxiliary space; iterative tree traversal needs an explicit stack or queue (O(h) for depth-first, up to O(n) for breadth-first) unless Morris traversal is used. Recursive traversal uses O(h) stack space: O(log n) for a balanced tree and O(n) for a linked list or skewed tree.

Linked Lists Versus Arrays

Operation Array Linked List
Access by index O(1) O(n)
Insert or delete at a known node or position O(n) because elements shift O(1) when the node handle is known
Append Amortized O(1); O(n) worst case during resizing O(1) with a maintained tail reference; otherwise O(n)
Memory layout Contiguous, with low per-element overhead Linked nodes, with additional pointer overhead
Cache locality Usually better Usually worse

Practical Example and Edge Cases

Searching 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> None for 6 visits six nodes in a linked list. In a balanced tree containing the same values, a search starting at root 4 visits 4 and then 6, requiring two comparisons.

  • Empty input: A list search returns immediately, while a tree search receives None as its root.

  • One element: Both structures require O(1) time for a successful search.

  • Duplicates: Linked lists allow duplicates; define whether a tree retains duplicate keys or applies a consistent duplicate-handling policy.

  • Negative numbers: Ordered-tree comparisons work normally with negative values.

  • Already sorted input: Sorting does not improve a linked list’s O(n) worst-case search cost. It can simplify construction of a balanced tree from sorted values, although the construction method determines its complexity.

  • Cycles: A linked list may contain a cycle, so linear searches must assume an acyclic list unless cycle detection is added. A tree is acyclic by definition.

  • Disconnected graphs: This concern does not directly apply to either structure.

Common Pitfalls

  • Assuming every tree is balanced; identify whether it is balanced, skewed, or unspecified.

  • Comparing insertion costs without including the cost of finding the insertion position.

  • Treating a linked list as random-access storage.

  • Forgetting to preserve the required successor link before modifying or deleting a node.

  • Ignoring recursion-stack cost when analyzing recursive traversal.

  • Common follow-up questions include reversing a list, detecting a cycle, merging sorted lists, and implementing balanced-tree rotations.

12

When should a linked list replace a hash table?

Use a linked list instead of a hash table when you need frequent insertions or deletions using existing node references, while performing few key-based lookups. A hash table is preferable when fast lookup, update, or removal by key is the primary requirement.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

When a Linked List Is Better

Choose a linked list when:

  • Node references are already available: Inserting after a known node or deleting a known node with its predecessor takes constant time.

  • Order must be explicit: Nodes remain in a defined sequence and can be traversed in either direction in a doubly linked list.

  • Sublists must be spliced or reordered: Connecting or separating chains of nodes does not require copying their contents.

  • Hashing is undesirable: A linked list avoids hash computation, collision handling, and hash-table resizing.

  • Duplicates are meaningful: A linked list can store duplicate values, whereas a dictionary or set normally enforces unique keys.

  • The data represents a sequence naturally: Examples include playlists, dependency chains, linked work queues, and adjacency lists.

The important qualification is that finding the required node in a linked list takes O(n). Therefore, a linked list is usually not faster than a hash table when the main operation is lookup by an arbitrary key.

Complexity Comparison

Operation Data structure Best Average Worst Reason
Access by index Linked list O(1) O(n) O(n) Index 0 is the head; later nodes require sequential traversal
Search by key/value Linked list O(1) O(n) O(n) The first node may match; otherwise nodes are inspected sequentially
Insert after known node Linked list O(1) O(1) O(1) A few links are updated
Delete known node and predecessor Linked list O(1) O(1) O(1) The surrounding links are bypassed
Append with maintained tail Linked list O(1) O(1) O(1) The new node is attached to the tail
Lookup by key Hash table O(1) O(1) O(n) Collisions or resizing can increase work
Insert by key Hash table O(1) O(1) O(n) A collision or full-table resize can require substantial work
Delete by key Hash table O(1) O(1) O(n) The key must be found before its entry is removed

For n elements, both structures require O(n) total space when the stored elements are counted. A traversal uses O(1) auxiliary space in both structures and no recursion stack. A hash table additionally maintains an O(n) bucket array and stored entries; a linked list stores one or more links per node.

Linked List Versus Array

Operation Linked list Array or dynamic list
Access by index O(n) O(1)
Insert/delete at a known node O(1), given the necessary links O(n), because elements may shift
Memory usage Higher per element due to node and pointer overhead Lower and more compact
Cache locality Usually poorer Usually better
Node replacement Possible without affecting other references Elements remain in fixed positions

For example, a singly linked list containing 1 -> 2 -> 3 -> None can insert 4 after 2 by changing two links, producing 1 -> 2 -> 4 -> 3 -> None. The operation is O(1), but locating 2 beforehand is O(n).

Practical Trade-offs

A hash table is the better choice for:

  • Repeated lookup by identifier, such as finding a user by ID.

  • Updating or deleting an item by key.

  • Counting occurrences or checking membership.

  • Avoiding repeated linear searches over a collection.

A linked list is the better choice for maintaining explicit ordering or changing relationships between already located nodes. In many real applications, a hash table plus a doubly linked list is combined: the hash table provides fast key lookup, while the linked list supports ordered traversal and constant-time removal of an entry when its node reference is known.

Common Pitfalls

  • Do not claim that linked-list insertion is always faster: it is O(n) unless the insertion location is already known.

  • In a singly linked list, deleting a node requires access to its predecessor; a doubly linked list can use prev directly.

  • Appending is O(1) only when a tail pointer is maintained; otherwise, locating the tail is O(n).

  • Do not use a hash table when sorted traversal is required. Hash tables do not naturally maintain sorted order.

  • Avoid using a linked list when memory overhead or cache performance are important; a dynamic array or collections.deque may be preferable.

13

Is O(√n) linked-list traversal possible with jump pointers?

A full linked-list traversal cannot run in O(√n) because producing every element requires visiting all n nodes. Jump pointers can reduce selected operations—such as indexed access or reaching the tail—to O(√n), but they require O(n) preprocessing and O(√n) auxiliary storage.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Full Traversal Versus Jump Operations

Suppose every element must be returned:

  • Visiting all nodes requires O(n) time in the best, average, and worst cases.

  • This is a lower bound of Ω(n): an algorithm cannot output n values without inspecting all n nodes.

  • Jump pointers skip blocks of nodes; therefore, following them does not constitute a full traversal.

With a block size of approximately √n:

  • Preprocessing the list takes O(n) time.

  • Following the jump chain to the tail takes O(√n) time.

  • Accessing an arbitrary indexed node takes O(√n) time.

How Jump Pointers Work

Divide the list into blocks containing approximately √n elements. Store an auxiliary pointer at each block boundary so the chain can move directly between blocks.

For the list:

1 -> 2 -> 3 -> 4 -> 5 -> None

With a block size of two, the auxiliary chain is:

J(1) -> J(3) -> J(5)

The linked list itself is unchanged:

1 -> 2 -> 3 -> 4 -> 5 -> None

To access index 4, calculate:

  • Block number: 4 // 2 = 2

  • Position within the block: 4 % 2 = 0

Follow two jump pointers to node 5, then move zero additional steps.

A dummy head simplifies empty-list handling and avoids separate logic for operations involving the first real node.

Complexity

Operation Best Average Worst Auxiliary Space
Full traversal O(n) O(n) O(n) O(1)
Build jump index O(n) O(n) O(n) O(√n)
Follow jump chain to tail O(√n) O(√n) O(√n) O(1)
Access by index O(1) O(√n) O(√n) O(1)

The indexed-access average assumes uniformly distributed positions. No recursion is used, so the recursion stack is O(1). Auxiliary-space figures exclude the input list; including the input, total storage is O(n).

Compared with arrays:

Operation Linked List Array
Access by index O(n) O(1)
Insert after a known node O(1) O(n) shifting
Delete with a known predecessor O(1) O(n) shifting

Common Pitfalls and Interview Tips

  • Misleading complexity: O(√n) applies to jump-chain operations after preprocessing, not to visiting every element.

  • Mutating the list: Insertions or deletions invalidate previously stored jump pointers unless the index is updated.

  • Cycles: An unguarded length calculation loops forever; check for a cycle with Floyd’s algorithm before building the index.

  • Edge cases: Handle empty and one-element lists explicitly (no jump pointers are needed). Duplicate and negative values work normally, and sorted order is irrelevant.

  • Graph terminology: Disconnected graphs do not apply to an ordinary singly linked list.

  • Common follow-up: Discuss indexed access, update invalidation, and whether dynamic jump pointers could be maintained without rebuilding the index.

14

How can skip lists enable O(log n) search in sorted linked lists?

A plain sorted linked list cannot support standard binary search in O(log n) because accessing its midpoint requires linear traversal. A skip list adds multiple levels of forward pointers, allowing searches to skip large sections of the list and achieve expected O(log n) time.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Why Plain Binary Search Fails on a Linked List

Binary search requires repeated access to the middle element. In an array, that access is O(1); in a linked list, finding the middle node is O(n).

Structure and operation Best time Average time Worst time Extra space
Sorted array binary search O(log n) O(log n) O(log n) O(1)
Plain linked-list binary search O(n) O(n) O(n) O(1)
Randomized skip-list search O(log n) O(log n) expected O(n) O(1) auxiliary

A skip list is therefore not literally array-based binary search. It uses several linked levels to perform the equivalent of narrowing the search range without repeatedly walking the entire list.

How Skip-List Search Works

The bottom level, level 0, contains every node in sorted order. Higher levels contain progressively fewer nodes. A sentinel head node (with value -inf) is used to simplify edge cases: it eliminates special checks for insertion at the head and guarantees that every search starts from a valid node.

During a search:

  1. Start at the highest level and the list head.

  2. Move forward while the next node is still less than the target.

  3. Descend to the next lower level.

  4. Repeat until level 0 is reached.

  5. Compare the next level-0 node with the target.

The search follows the forward pointers rather than repeatedly traversing from the head. The implementation below also maintains the ordinary next pointer for level 0.

For a target of 8, the list remains:

1 -> 2 -> 3 -> 5 -> 8 -> 13 -> None

The search skips over values below 8 using higher levels, descends to level 0, finds 8, and returns it. The list is not modified:

1 -> 2 -> 3 -> 5 -> 8 -> 13 -> None

Code Example

from __future__ import annotations

import random


class ListNode:
    def __init__(self, val: int | float, level: int = 1) -> None:
        self.val = val
        self.next: ListNode | None = None
        self.forward: list[ListNode | None] = [None] * level


def _forward(node: ListNode, level: int) -> ListNode | None:
    """Return the forward pointer at a level, if the node has one."""
    if level < len(node.forward):
        return node.forward[level]
    return None


def _random_level(rng: random.Random, max_level: int) -> int:
    """Choose a node level using the usual skip-list coin-flip method."""
    level = 1
    while level < max_level and rng.getrandbits(1) == 0:
        level += 1
    return level


def build_skip_list(values: list[int], seed: int = 7) -> ListNode:
    """Build a skip list from values already sorted in ascending order."""
    max_level = max(1, len(values).bit_length())
    head = ListNode(float("-inf"), max_level)  # sentinel head simplifies edge cases
    rng = random.Random(seed)

    for value in values:
        new_node = ListNode(value, _random_level(rng, max_level))
        update: list[ListNode] = [head] * max_level
        current = head

        # Find the predecessor at every level.
        for level in range(max_level - 1, -1, -1):
            while True:
                candidate = _forward(current, level)
                if candidate is None or candidate.val >= value:
                    break
                current = candidate
            update[level] = current

        # Insert the node at the levels it owns.
        for level in range(len(new_node.forward)):
            successor = _forward(update[level], level)
            new_node.forward[level] = successor
            update[level].forward[level] = new_node

            if level == 0:
                new_node.next = successor
                update[level].next = new_node

    return head


def binary_search_skip_list(head: ListNode, target: int) -> ListNode | None:
    """Search a sorted skip list and return a node equal to target."""
    current = head

    for level in range(len(head.forward) - 1, -1, -1):
        while True:
            candidate = _forward(current, level)
            if candidate is None or candidate.val >= target:
                break
            current = candidate

    candidate = _forward(current, 0)
    if candidate is not None and candidate.val == target:
        return candidate
    return None


head = build_skip_list([1, 2, 3, 5, 8, 13])
found = binary_search_skip_list(head, 8)
print(found.val if found is not None else None)  # 8

The random seed makes the example reproducible; the expected O(log n) bound assumes the node levels are generated using the randomized distribution.

Common Pitfalls

  • Calling plain linked-list binary search O(log n): the midpoint lookup still costs O(n).

  • Assuming skip-list search is always O(log n): it is expected O(log n); an unfavorable level distribution can make this implementation O(n).

  • Forgetting to update next: it must remain consistent with forward[0].

  • Empty input: the search returns None.

  • One element: the target is found correctly.

  • Duplicate values: the structure supports them, and the search returns one matching node.

  • Negative values: the sentinel uses negative infinity, so ordering remains correct.

  • Cycles: they violate the sorted-list invariant and would cause non-terminating traversal.

  • Guaranteed worst-case O(log n): use a deterministic indexed linked list or a balanced search tree instead of a randomized skip list.

15

Can binary search achieve O(n) on a doubly linked list?

Yes—binary search on a sorted doubly linked list can run in O(n) total time by combining logarithmic comparisons with the pointer movement required to reach each midpoint. The list is traversed only a linear number of times overall, although the binary-search comparison count is O(log n).

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

Unlike an array, a linked list does not provide constant-time access by index. Therefore, a midpoint cannot be computed and accessed in O(1).

An O(n) implementation follows these steps:

  1. Find the initial midpoint, for example using fast and slow pointers, which traverse the list once.

  2. Compare the target with the midpoint node’s value.

  3. If the target is smaller, use prev pointers to reach the midpoint of the remaining left half.

  4. If the target is larger, use next pointers to reach the midpoint of the remaining right half.

  5. Continue until the target is found or the candidate interval becomes empty.

The conceptual index bounds can be tracked even though the list cannot be indexed directly. Moving between successive midpoints takes time proportional to the current candidate interval. Since those intervals shrink by roughly half, the total pointer movement forms a geometric series and is O(n).

A dummy sentinel head gives the first node a stable predecessor, making backward movement safer. If its prev pointer is temporarily changed, the original pointer must be restored after the search.

Complexity

  • Best-case time: O(n), because locating the initial midpoint already requires linear traversal.

  • Average-case time: O(n), because the total movement across all visited intervals is linear.

  • Worst-case time: O(n), including when the target is absent.

  • Value comparisons: O(log n), because each comparison halves the candidate interval.

  • Auxiliary space: O(1), including the recursion stack; the implementation is iterative. The input list is not counted. If input memory is counted, total space is O(n).

Scanning from the start of the remaining interval also totals O(n), because the intervals halve. Rescanning from the head of the whole list for every midpoint is what costs O(n log n); moving from the current midpoint with prev or next avoids it.

Doubly Linked List vs Array

Operation Doubly linked list without an index Array
Access by index O(n) O(1)
Search in sorted data O(n) O(log n)
Insert or delete after a known node O(1) O(n) due to shifting
Extra storage for indexed binary search O(n) for an index-to-node table O(1); no separate index is needed

Building a dense index-to-node table once takes O(n) time and space. Later searches can access each indexed node in O(1) and run in O(log n) time, provided the table is rebuilt after structural modifications. A hash map from index to node gives expected O(log n) search time, but its worst-case lookup behavior differs from a dense table.

Example Walkthrough

Before searching, the list is:

1 -> 2 -> 3 -> 4 -> 5 -> None

When searching for 4:

  1. The initial midpoint is node 3.

  2. Since 4 > 3, the candidate interval becomes nodes 4 and 5.

  3. Moving forward reaches node 4.

  4. The values match, so the search returns node 4.

After the operation, the list remains unchanged:

1 -> 2 -> 3 -> 4 -> 5 -> None

Common Pitfalls

  • Off-by-one errors: Keep the candidate interval boundaries inclusive and update them before calculating the next midpoint.

  • False random-access assumptions: A computed index cannot be used to access a linked-list node directly.

  • Repeated full traversals: Restarting midpoint discovery from the head for every comparison can raise the running time to O(n log n).

  • Input mutation: A temporary dummy sentinel must not leave head.prev permanently modified.

  • Invalid input: The list must be sorted in ascending order, finite, acyclic, and have consistent next and prev pointers. Empty lists, single-node lists, duplicates, and negative values are otherwise handled normally.

  • Common follow-up: Interviewers may ask how an index-to-node table would affect repeated searches, how list modifications affect the index, or how Floyd’s algorithm detects cycles.

16

How do you find the middle element of a linked list?

The middle element can be found using fast and slow pointers: the fast pointer advances two nodes while the slow pointer advances one. This implementation returns the second middle node for an even-length list, following the common LeetCode convention.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Approach

  1. Create a dummy sentinel node before the list head. This keeps pointer logic consistent and simplifies empty-list handling.

  2. Use Floyd’s cycle detection first. A cyclic list has no well-defined middle, so the method raises ValueError.

  3. Start slow at the dummy node and fast at the first actual node.

  4. Move slow one node and fast two nodes until fast reaches the end.

  5. Return slow.next.

For an odd-length list, slow.next is the single middle node. For an even-length list, it is the second of the two middle nodes.

Approach Comparison

Approach Time Space When to use
Two-pass (count length, then traverse to middle) O(n) O(1) Simple to understand; useful when length is needed for other reasons.
Fast and slow pointers (single pass) O(n) O(1) Optimal for just finding the middle; one traversal, no extra storage.

The fast-and-slow method is preferred in interviews because it finds the middle in one pass.

Walkthrough

For the list dummy -> 1 -> 2 -> 3 -> 4 -> None:

Step slow fast
Initial dummy 1
Iteration 1 1 3
Iteration 2 2 None

The method returns slow.next, which is 3.

The operation does not modify the list:

  • Before: 1 -> 2 -> 3 -> 4 -> None

  • After: 1 -> 2 -> 3 -> 4 -> None

Complexity

Case Time Reason
Best O(1) Empty or single-node lists return immediately.
Average O(n) Both pointers process a proportional number of nodes.
Worst O(n) Both the cycle check and middle search traverse at most the list length.
  • Auxiliary space: O(1), because only pointers and one sentinel node are used.

  • The input list is not counted, and there is no recursion stack.

Linked Lists vs Arrays

Operation Linked list Array
Access by index O(n) O(1)
Insert after a known node O(1) O(n), due to shifting
Delete after a known node O(1) O(n), due to shifting
Insert or delete at the beginning O(1) O(n), due to shifting

Linked lists favor frequent structural changes, while arrays favor constant-time indexed access and compact storage.

Code Example

from __future__ import annotations

from dataclasses import dataclass


@dataclass(slots=True)
class ListNode:
    val: int
    next: ListNode | None = None


class LinkedList:
    def __init__(self, head: ListNode | None = None) -> None:
        self.head = head

    def find_middle(self) -> ListNode | None:
        """Return the middle node, or the second middle node if length is even."""
        dummy = ListNode(0, self.head)

        if dummy.next is None:
            return None

        # Detect cycles with Floyd's algorithm because a cyclic list
        # does not have a well-defined middle element.
        cycle_slow = dummy.next
        cycle_fast = dummy.next

        while cycle_fast is not None and cycle_fast.next is not None:
            cycle_slow = cycle_slow.next
            cycle_fast = cycle_fast.next.next

            if cycle_slow is cycle_fast:
                raise ValueError("The linked list contains a cycle")

        # Find the middle. Starting slow at the sentinel keeps the
        # pointer offset consistent for odd and even list lengths.
        slow = dummy
        fast = dummy.next

        while fast is not None and fast.next is not None:
            slow = slow.next
            fast = fast.next.next

        assert slow is not None
        return slow.next


head = ListNode(1, ListNode(2, ListNode(3, ListNode(4))))
middle = LinkedList(head).find_middle()
print(middle.val if middle is not None else None)  # 3

Common Pitfalls

  • Even-length ambiguity: This returns the second middle node. To return the first, adjust the final return value.

  • Cyclic lists: Without cycle detection, the pointer loop may never terminate.

  • Incorrect comparisons: Compare node identity with is, not ==.

  • Null access: Check fast and fast.next before advancing them.

  • Mutation: Finding the middle should not rearrange or remove nodes.

  • Edge cases: Empty input returns None; one element returns that element; duplicate and negative values do not affect the result.

17

How do you implement a stack using a linked list in Python 3.12?

A linked-list-based stack implements the stack ADT by treating the head of a singly linked list as the top element. push inserts a node at the head, while pop removes the head node, giving both operations constant-time performance.

Read full answer

Applies toPython 3.12

How It Works

The implementation uses a dummy sentinel head node. The sentinel is not part of the user-visible stack and simplifies insertion and removal because the list never needs special handling for an empty head.

  • The node after the sentinel is the stack’s top.

  • push(value) creates a new node whose next points to the current top.

  • pop() removes the top node and returns its value.

  • peek() returns the top value without removing it.

  • The traversal order is LIFO: the most recently pushed value is returned first.

For example, after pushing 10, 20, and 30, the logical list state is:

30 -> 20 -> 10 -> None

After pop(), the returned value is 30, and the state becomes:

20 -> 10 -> None

Complexity

Operation Best case Average case Worst case Space
push O(1) O(1) O(1) O(1) auxiliary
pop O(1) O(1) O(1) O(1) auxiliary
peek O(1) O(1) O(1) O(1) auxiliary
Traversing all values O(n) O(n) O(n) O(1) auxiliary

The operations are O(1) because they modify only the first few pointers. Traversing all values is O(n) because each node is visited once. There is no recursion, so the recursion stack is O(1). The stack itself stores O(n) nodes; the input is not counted separately in these auxiliary-space figures.

Comparison with Arrays

Capability Linked-list stack Array-based stack
Access by index O(n) O(1)
Insert at a known node O(1) O(n)
Delete at a known node O(1) O(n)
Push and pop at the top O(1) O(1) amortized
Total storage for n values O(n) O(n)
Resizing Not required May require an occasional O(n) copy

A linked-list stack avoids array resizing and provides efficient head insertion and deletion. An array-backed stack is often simpler and may have better cache locality when the stack size is known or changes infrequently.

Code Example

from __future__ import annotations

from collections.abc import Iterator


class ListNode:
    """A node in a singly linked list."""

    def __init__(self, val: int, next: ListNode | None = None) -> None:
        self.val = val
        self.next = next


class StackLinkedList:
    """A LIFO stack implemented with a singly linked list."""

    def __init__(self) -> None:
        self._head = ListNode(0)  # Dummy sentinel node
        self._size = 0

    def push(self, value: int) -> None:
        """Insert value at the top of the stack."""
        new_node = ListNode(value, self._head.next)
        self._head.next = new_node
        self._size += 1

    def pop(self) -> int:
        """Remove and return the value at the top of the stack."""
        if self._head.next is None:
            raise IndexError("pop from an empty stack")

        top_node = self._head.next
        self._head.next = top_node.next
        top_node.next = None
        self._size -= 1
        return top_node.val

    def peek(self) -> int:
        """Return the top value without removing it."""
        if self._head.next is None:
            raise IndexError("peek from an empty stack")

        return self._head.next.val

    def is_empty(self) -> bool:
        """Return whether the stack contains no values."""
        return self._size == 0

    def __len__(self) -> int:
        return self._size

    def __iter__(self) -> Iterator[int]:
        """Yield values from the top of the stack to the bottom."""
        current = self._head.next
        while current is not None:
            yield current.val
            current = current.next


if __name__ == "__main__":
    stack = StackLinkedList()
    stack.push(10)
    stack.push(20)
    stack.push(30)

    print(stack.pop())  # Expected output: 30

Common Pitfalls and Interview Tips

  • Empty stack: pop() and peek() should explicitly raise IndexError rather than dereferencing None.

  • Sentinel handling: The dummy head must never be returned as a stack value.

  • Node detachment: Clear the removed node’s next reference when appropriate to avoid accidental retention of old nodes.

  • Value edge cases: Duplicate and negative values are supported normally. A one-element stack works with the same code.

  • Already sorted input: Not applicable; a stack preserves insertion order and does not require sorted input.

  • Disconnected graphs and cycles: Not applicable to a basic stack implementation. If the structure is extended into a general linked list, cycle detection with fast and slow pointers becomes relevant.

  • Common follow-up: Explain why inserting and deleting at the head is O(1), and compare this design with using a Python list as a stack.

18

Reverse a Singly Linked List with Two Pointers

Reverse a singly linked list by changing each node’s next pointer in place using two-pointer reversal. A dummy head stores the returned head, allowing empty and nonempty lists to use the same return path.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

The two traversal pointers are:

  • prev: the last node of the already-reversed portion.

  • curr: the node currently being processed.

Before changing curr.next, save its original successor in next_node. Then reverse the link, advance prev to curr, and continue from next_node.

The dummy head is separate from the list’s nodes. After the traversal, dummy_head.next is assigned the new head and returned; this avoids special-casing how the caller receives the head.

Example walkthrough:

  1. Before: 1 -> 2 -> 3 -> None

  2. Save node 2, reverse node 1, and make prev = 1: 1 -> None

  3. Save node 3, reverse node 2, and make prev = 2: 2 -> 1 -> None

  4. Save None, reverse node 3, and make prev = 3: 3 -> 2 -> 1 -> None

  5. Assign the new head to the dummy head and return it.

  6. After: 3 -> 2 -> 1 -> None

Code Example

from __future__ import annotations


class ListNode:
    def __init__(self, val: int, next: ListNode | None = None) -> None:
        self.val = val
        self.next = next


def reverse_linked_list(head: ListNode | None) -> ListNode | None:
    """Reverse a singly linked list in place using two traversal pointers."""
    dummy_head = ListNode(0)

    prev: ListNode | None = None
    curr = head

    while curr is not None:
        # Save the original successor before overwriting curr.next.
        next_node = curr.next

        # Reverse this link and advance the two traversal pointers.
        curr.next = prev
        prev = curr
        curr = next_node

    # The dummy head holds the new head without becoming part of the list.
    dummy_head.next = prev
    return dummy_head.next


head = ListNode(1, ListNode(2, ListNode(3)))
new_head = reverse_linked_list(head)

# Expected output: 3 -> 2 -> 1 -> None

Complexity

  • Best case: O(n) — every node must be processed to reverse the list.

  • Average case: O(n) — the traversal processes each node once.

  • Worst case: O(n) — the traversal processes each node once.

  • Auxiliary space: O(1) — only two traversal pointers, one saved successor, and one dummy node are used. There is no recursion stack, and the input is modified rather than copied. Input storage is not counted as auxiliary space.

Here, n is the number of nodes.

Linked Lists vs Arrays

Operation Singly linked list Array
Access by index O(n) O(1)
Insert after a known node O(1) O(n) due to shifting
Delete after a known node/index O(1) for a known node O(n) due to shifting
In-place reversal O(n) time, O(1) auxiliary space O(n) time, O(1) auxiliary space

Linked lists favor frequent insertions and deletions when a node reference is already available. Arrays favor constant-time indexed access.

Common Pitfalls

  • Losing the original successor: Save curr.next in next_node before overwriting it.

  • Returning the old head: The caller must use the returned new_head; the original head variable still references the old head, which is now the tail.

  • Forgetting the sentinel: The dummy node must not become part of the returned list.

  • Mutating the input: This algorithm reverses the original nodes in place. Copy the nodes first if the caller must retain the original order.

  • Empty input: The function returns None.

  • One node: The function returns the same node, now ending with None.

  • Duplicate or negative values: Values do not affect pointer reversal.

  • Already sorted input: It is reversed normally; no special handling is required.

  • Cycles: A cyclic list is unsupported and would cause nontermination. Detect and break the cycle separately if needed.

  • Disconnected graphs: Not applicable to this singly linked-list operation.

  • Typical follow-up: Interviewers may ask how to reverse only the sublist between two given nodes while leaving the prefix and suffix unchanged.

19

How do you convert a singly linked list into a circular one?

A circular linked list is a singly linked list whose last node points back to the first node instead of to None. The conversion finds the tail node and changes its next pointer to the first node.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

The algorithm is:

  1. Create or use a dummy sentinel head to provide a stable entry point.

  2. If the list is empty, leave it empty.

  3. Detect whether the list already contains a cycle using Floyd’s fast-and-slow-pointer algorithm.

  4. Traverse to the final node.

  5. Set the tail’s next pointer to the first data node.

Using a sentinel avoids repeatedly handling the list’s first node separately. In the example, the sentinel remains before the circular portion:

Sentinel -> 1 -> 2 -> 3 -> 1

The circular data path is:

1 -> 2 -> 3 -> 1

Example Walkthrough

Before conversion:

1 -> 2 -> 3 -> None
Step Current state
Start 1 -> 2 -> 3 -> None
Find tail 1 -> 2 -> 3 -> None
Redirect tail 1 -> 2 -> 3 -> 1

For a single-node list, the result is 1 -> 1. For an empty list, there is no node to link back, so it remains empty.

Complexity

For n data nodes:

  • Best-case time: O(1) for an empty or single-node list.

  • Average-case time: O(n) because Floyd’s cycle detection and tail traversal each visit at most n nodes.

  • Worst-case time: O(n).

  • Auxiliary space: O(1) for the sentinel and pointer variables. The input list itself is not counted; including the existing nodes, total storage is O(n).

  • Recursion stack: None, because the implementation is iterative.

Linked Lists vs Arrays

Operation Array Singly linked list
Access by index O(1) O(n)
Insert at a known node O(n) because elements shift O(1)
Delete at a known node O(n) because elements shift O(1)
Find the tail O(1) with stored length O(n)

Linked lists are useful when frequent insertion or deletion is more important than random indexed access.

Code Example

from __future__ import annotations


class ListNode:
    """Node in a singly linked list."""

    def __init__(self, val: int, next: ListNode | None = None) -> None:
        self.val = val
        self.next = next


def convert_to_circular(dummy: ListNode) -> ListNode:
    """Convert a sentinel-headed singly linked list into circular form."""
    first = dummy.next

    # Empty list: there is no tail that can point to a first node.
    if first is None:
        return dummy

    # Floyd's algorithm: detect whether the list is already circular.
    slow = first
    fast = first

    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next

        if slow is fast:
            # Already circular; no conversion is needed.
            return dummy

    # Find the tail of the acyclic list.
    tail = first
    while tail.next is not None:
        tail = tail.next

    # Convert the terminating None into a link to the first node.
    tail.next = first
    return dummy


def circular_values(dummy: ListNode) -> list[int]:
    """Read one complete traversal of a circular list without looping forever."""
    values: list[int] = []
    visited: set[int] = set()
    current = dummy.next

    while current is not None and id(current) not in visited:
        visited.add(id(current))
        values.append(current.val)
        current = current.next

    return values


dummy = ListNode(0)
dummy.next = ListNode(1)
dummy.next.next = ListNode(2)
dummy.next.next.next = ListNode(3)

result = convert_to_circular(dummy)
print(circular_values(result))
# Expected output: [1, 2, 3]

Common Pitfalls

  • Forgetting the empty case: Attempting to access the tail of an empty list causes a null-reference error.

  • Stopping at None: After conversion, the tail points to the first node, so traversal can continue indefinitely unless a visited set or cycle-detection algorithm is used.

  • Confusing the sentinel with the first data node: With this representation, dummy.next is the first data node. The sentinel itself is not part of the circular data path.

  • Assuming sorted or unique values: Sorting and duplicates do not affect conversion because node identity, not node value, determines the links.

  • Mutating the input unexpectedly: This operation changes the original nodes by updating the tail’s next pointer.

  • Interview follow-up: Interviewers may ask how to detect a cycle, convert the list back to an acyclic list, or return the first node instead of the sentinel.

20

How to convert a singly linked list into a doubly linked list?

A doubly linked list is produced by creating one new node for each singly linked node and connecting both the next and prev pointers. The original values and their order are preserved, while the source list remains unchanged.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How the Conversion Works

Traverse the singly linked list from head to tail while maintaining the last node created in the destination list.

  1. Allocate a dummy head node, which simplifies empty-list handling and eliminates repeated checks for the first node.

  2. For each source node:

  3. Create a destination node with the same value.

  4. Set its prev pointer to the destination tail.

  5. Set the tail’s next pointer to the new node.

  6. Advance the destination tail.

  7. Detach the dummy node by setting the first destination node’s prev pointer to None.

  8. Return the dummy node’s next pointer.

This implementation creates new nodes. If the existing nodes can be extended with a prev field, they can instead be updated in place using a prev and current pointer traversal.

Complexity

Let n be the number of nodes.

  • Best-case time: O(n) — every source node is visited.

  • Average-case time: O(n) — every source node is visited regardless of the values.

  • Worst-case time: O(n) — cycle detection and conversion each perform at most a linear traversal.

  • Auxiliary space: O(1), excluding the input and returned output. Only pointers and one dummy node are required.

  • Output space: O(n) because the conversion creates n destination nodes.

  • Recursion stack: O(1) because the implementation is iterative.

Thus, the total additional space, including the returned list, is O(n).

Example Walkthrough

Input:

1 -> 2 -> 3 -> None

Using the dummy node during construction:

  1. Start: dummy -> None

  2. Copy 1: dummy <-> 1

  3. Copy 2: dummy <-> 1 <-> 2

  4. Copy 3: dummy <-> 1 <-> 2 <-> 3

  5. Remove the dummy sentinel from the result.

Final doubly linked list:

None <- 1 <-> 2 <-> 3 -> None

Linked Lists Compared with Arrays

Operation Array Singly linked list Doubly linked list
Access by index O(1) O(n) O(n)
Insert after a known node O(n) due to shifting O(1) O(1)
Delete a known node O(n) due to shifting O(n) to find its predecessor O(1)
Access the previous node O(n) O(n) O(1)
Memory per element Contiguous storage Value, next Value, next, prev

A doubly linked list is useful when traversal in both directions is required, but it uses additional memory for every prev pointer.

Code Example

from __future__ import annotations


class ListNode:
    """Node used for both singly and doubly linked-list examples."""

    def __init__(
        self,
        val: int,
        next: ListNode | None = None,
        prev: ListNode | None = None,
    ) -> None:
        self.val = val
        self.next = next
        self.prev = prev


def _has_cycle(head: ListNode | None) -> bool:
    """Detect a cycle with Floyd's fast and slow pointer algorithm."""
    slow = head
    fast = head

    while fast is not None:
        next_node = fast.next
        if next_node is None:
            return False

        assert slow is not None
        slow = slow.next
        fast = next_node.next

        if slow is fast:
            return True

    return False


def convert_to_doubly(head: ListNode | None) -> ListNode | None:
    """Return a new doubly linked list with the same values and order.

    Raises:
        ValueError: If the source list contains a cycle.
    """
    if _has_cycle(head):
        raise ValueError("The source linked list contains a cycle")

    # Dummy head simplifies appending the first and subsequent nodes.
    dummy = ListNode(0)
    tail = dummy
    current = head

    while current is not None:
        new_node = ListNode(current.val)
        new_node.prev = tail
        tail.next = new_node

        tail = new_node
        current = current.next

    result = dummy.next

    # The returned list should not expose the dummy sentinel.
    if result is not None:
        result.prev = None

    return result


def _forward_values(head: ListNode | None) -> list[int]:
    """Return the values stored in a finite linked list."""
    values: list[int] = []
    current = head

    while current is not None:
        values.append(current.val)
        current = current.next

    return values


source = ListNode(1, ListNode(2, ListNode(3)))
result = convert_to_doubly(source)

print(_forward_values(result))  # Expected: [1, 2, 3]

assert result is not None
assert result.prev is None
assert result.next is not None
assert result.next.prev is result

The implementation handles an empty list by returning None and a one-element list by producing a node whose prev and next are both None. Duplicate and negative values are preserved exactly. Sorted input requires no special handling because only order, not value comparisons, matters.

Common Pitfalls and Interview Tips

  • Forgetting a back-link: Every new node’s prev must point to the preceding destination node.

  • Returning the dummy node: Return dummy.next, and normally detach the first result node from the sentinel.

  • Accidentally mutating the input: Save current.next before changing any links if an in-place variant is used.

  • Repeated insertion at the front: Building the result with repeated insert(0, node) or equivalent operations can become O(n²).

  • Ignoring cycles: A cyclic source would otherwise cause an infinite traversal. The example detects it using Floyd’s algorithm and raises ValueError.

  • Disconnected graphs: They do not apply to this operation because only one linked list is processed.

Common interview follow-ups include converting in place, reversing a doubly linked list, detecting a cycle with prev pointers, and explaining why deletion is easier when a node’s predecessor is directly accessible.

21

How do you implement a doubly linked list with a stack?

A stack-assisted doubly linked list stores each value in a node containing val, next, and prev pointers, while a LIFO stack supports operations such as reversal. Using stacks as the primary storage would make arbitrary-node access O(n); keeping direct links preserves O(1) insertion and removal when the target node is already known.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

  • Sentinel nodes: A dummy head and tail simplify updates and eliminate special cases for empty or single-element lists.

  • Forward links: next moves toward the tail.

  • Backward links: prev moves toward the head.

  • Stack-assisted reversal: Nodes are pushed into a stack, then popped and their next and prev references are swapped.

  • No recursion: The implementation avoids the recursion stack and Python’s recursion-depth limit.

The externally visible state changes from:

1 -> 2 -> 3 -> None

to:

3 -> 2 -> 1 -> None

Internally, the list is circular through its sentinels: head -> 1 -> 2 -> 3 -> tail, with backward links connecting tail to 1.

Operation Complexity

Operation Best Average Worst Auxiliary space
Push at either end O(1) O(1) O(1) O(1)
Insert after a known node O(1) O(1) O(1) O(1)
Remove a known node O(1) O(1) O(1) O(1)
Access by index O(n) O(n) O(n) O(1)
Stack-assisted reversal O(n) O(n) O(n) O(n)

The auxiliary-space figures exclude the list’s own O(n) node storage. The reversal stack requires O(n) additional space because every node is stored before the links are changed. If the stack requirement were removed, direct pointer reversal could achieve O(n) time with O(1) auxiliary space.

Code Example

from __future__ import annotations

from collections import deque
from collections.abc import Iterable


class ListNode:
    """A node in a doubly linked list."""

    def __init__(
        self,
        val: int = 0,
        next: ListNode | None = None,
        prev: ListNode | None = None,
    ) -> None:
        self.val = val
        self.next = next
        self.prev = prev


class DoublyLinkedList:
    """Doubly linked list with sentinel nodes and stack-assisted reversal."""

    def __init__(self, values: Iterable[int] = ()) -> None:
        self.head = ListNode()
        self.tail = ListNode()
        self.head.next = self.tail
        self.tail.prev = self.head

        current = self.head
        for value in values:
            node = ListNode(val=value, prev=current)
            current.next = node
            current = node

        current.next = self.tail
        self.tail.prev = current

    def push_front(self, value: int) -> ListNode:
        """Insert a node before the first data node."""
        first = self.head.next
        node = ListNode(val=value, next=first, prev=self.head)
        first.prev = node
        self.head.next = node
        return node

    def push_back(self, value: int) -> ListNode:
        """Insert a node after the last data node."""
        last = self.tail.prev
        node = ListNode(val=value, next=self.tail, prev=last)
        last.next = node
        self.tail.prev = node
        return node

    def insert_after(self, target: ListNode, value: int) -> ListNode:
        """Insert a node after a known node belonging to this list."""
        if target is self.tail:
            raise ValueError("Cannot insert after the tail sentinel")

        node = ListNode(val=value, next=target.next, prev=target)
        target.next.prev = node
        target.next = node
        return node

    def remove(self, node: ListNode) -> ListNode:
        """Remove and detach a known data node."""
        assert node is not self.head and node is not self.tail
        assert node.prev is not None and node.next is not None

        node.prev.next = node.next
        node.next.prev = node.prev
        node.prev = None
        node.next = None
        return node

    def reverse(self) -> None:
        """Reverse the list using a LIFO stack."""
        stack: deque[ListNode] = deque()
        current = self.head.next

        while current is not self.tail:
            stack.append(current)
            current = current.next

        if not stack:
            return

        new_first = stack[-1]   # original last node
        new_last = stack[0]     # original first node

        while stack:
            node = stack.pop()
            node.prev, node.next = node.next, node.prev

        # Fix sentinel links after pointer swap
        self.head.next = new_first
        new_first.prev = self.head
        self.tail.prev = new_last
        new_last.next = self.tail

    def to_list(self) -> list[int]:
        """Return the data-node values in forward order."""
        result: list[int] = []
        current = self.head.next

        while current is not self.tail:
            result.append(current.val)
            current = current.next

        return result


# Example usage
dll = DoublyLinkedList([1, 2, 3])
dll.reverse()
print(dll.to_list())  # [3, 2, 1]

Arrays vs. Doubly Linked Lists

Operation Array Doubly linked list
Access by index O(1) O(n)
Search by value O(n) O(n)
Insert near a known node/index O(n) due to shifting O(1) for a known node
Delete near a known node/index O(n) due to shifting O(1) for a known node
Memory per element Contiguous storage Node plus two pointers

Common Pitfalls

  • Do not stop traversal at None when using the sentinel design; stop when current is self.tail.

  • When removing a node, update both node.prev.next and node.next.prev.

  • Do not change links while traversing them directly; the stack isolates traversal from mutation.

  • Negative values and duplicates require no special handling because nodes, not values, define identity.

  • Empty and one-element lists work without special cases because of the sentinels.

Interview Tips

A common follow-up is reversing a DLL without a stack. That version uses prev, current, and next pointers and runs in O(n) time with O(1) auxiliary space. Other likely questions include merging two sorted lists, removing the nth node from the end, detecting a cycle with fast and slow pointers, and finding the list’s midpoint.

22

How do you convert a binary tree to a doubly linked list?

Inorder flattening converts a binary tree into a doubly linked list by visiting its nodes in left-root-right order. This implementation creates a new doubly linked list with fresh nodes, preserving the original tree.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Conversion Approach

The usual convention is to produce an inorder sequence. This ordering must be specified because preorder and postorder conversions are also possible.

  1. Perform an iterative inorder traversal of the binary tree.

  2. For each visited tree node, create a new ListNode with the same value.

  3. Append the new ListNode to the doubly linked list by updating the previous node’s next and the current node’s prev.

  4. Return the first non-sentinel node.

A temporary dummy head simplifies appending the first node without a special case. The dummy is removed from the public result by setting the returned head’s prev to None.

An explicit stack is used instead of recursion because a skewed tree can exceed Python’s default recursion limit.

Step-by-Step Example

Consider this tree:

4
       / \
      2   6
     / \
    1   3

The conceptual inorder sequence before conversion is:

1 -> 2 -> 3 -> 4 -> 6 -> None

The traversal and linking proceed as follows:

Step Tree node visited ListNode appended next chain
1 1 1 1 -> None
2 2 2 1 -> 2 -> None
3 3 3 1 -> 2 -> 3 -> None
4 4 4 1 -> 2 -> 3 -> 4 -> None
5 6 6 1 -> 2 -> 3 -> 4 -> 6 -> None

After conversion:

next: 1 -> 2 -> 3 -> 4 -> 6 -> None
prev: 6 -> 4 -> 3 -> 2 -> 1 -> None

Complexity

Let n be the number of tree nodes and h the tree height (counting edges).

  • Time: Best, average, and worst case are all O(n). Every node is pushed, popped, and a new list node is created and linked exactly once.

  • Auxiliary space (excluding output): O(h) for the explicit traversal stack. This is O(1) for a right-skewed tree, O(log n) for a balanced tree, and O(n) for a left-skewed tree.

  • Output space: O(n) for the new doubly linked list nodes.

  • No recursion stack is used.

Linked Lists vs Arrays

Operation Doubly linked list Array
Access by position O(n) O(1)
Search by value O(n) average O(n) average
Insert after a known node O(1) O(n) because elements shift
Delete a known node O(1) once its predecessor is known O(n) because elements shift
Memory per element Extra pointer overhead Contiguous storage

Code Example

from __future__ import annotations
from dataclasses import dataclass


@dataclass
class TreeNode:
    val: int
    left: TreeNode | None = None
    right: TreeNode | None = None


@dataclass
class ListNode:
    val: int
    next: ListNode | None = None
    prev: ListNode | None = None


def binary_tree_to_doubly_linked_list(
    root: TreeNode | None,
) -> ListNode | None:
    """Convert a binary tree to a doubly linked list using inorder traversal.

    Creates new ListNode objects, leaving the original tree unchanged.
    """
    stack: list[TreeNode] = []
    current = root

    # Dummy head avoids special-case handling for the first list node.
    dummy_head = ListNode(0)
    tail = dummy_head

    while current is not None or stack:
        # Descend to the next leftmost unvisited node.
        while current is not None:
            stack.append(current)
            current = current.left

        node = stack.pop()

        # Create a new list node for the current tree node.
        list_node = ListNode(node.val)

        # Append to the doubly linked list.
        tail.next = list_node
        list_node.prev = tail
        tail = list_node

        # Continue with the right subtree.
        current = node.right

    # Terminate the list and remove the dummy head.
    tail.next = None
    head = dummy_head.next
    if head is not None:
        head.prev = None

    return head


if __name__ == "__main__":
    tree = TreeNode(
        4,
        TreeNode(2, TreeNode(1), TreeNode(3)),
        TreeNode(6),
    )

    head = binary_tree_to_doubly_linked_list(tree)

    values: list[int] = []
    current = head
    while current is not None:
        values.append(current.val)
        current = current.next

    print(values)
    print(" -> ".join(map(str, values)) + " -> None")

    # Expected output:
    # [1, 2, 3, 4, 6]
    # 1 -> 2 -> 3 -> 4 -> 6 -> None

Common Pitfalls

  • Mutating input: This implementation does not mutate the original tree. If in-place conversion is required, reuse the tree nodes by treating left as prev and right as next.

  • Forgetting to terminate the list: The tail’s next must be set to None, and the head’s prev must be None.

  • Recursion depth: A recursive inorder traversal can hit Python’s recursion limit on skewed trees; an explicit stack avoids this.

  • Invalid inputs: An empty tree returns None; one node returns a single-node list; duplicates and negative values are preserved. An already inorder-shaped tree still produces the same sequence. Cyclic or disconnected structures are not valid binary trees.

  • Interview follow-up: Clarify whether the required ordering is inorder, preorder, or postorder, and discuss the trade-offs between creating a new list (O(n) extra space) and in-place conversion (O(1) extra space but destroys the tree).

23

How to insert a node at a specific linked list position

Position-based insertion finds the node immediately before the desired position, then changes one next pointer to insert the new node. A dummy head node simplifies insertion at the beginning by removing the need for a separate empty-list or new-head case.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

This implementation uses 1-based positions among the data nodes:

  • Position 1 inserts before the first data node.

  • Position 2 inserts between the first and second data nodes.

  • Position size + 1 appends after the last node.

The insertion procedure is:

  1. Validate that the position is between 1 and size + 1.

  2. Start at the dummy head and traverse position - 1 links.

  3. Create a new node whose next points to the old successor.

  4. Point the predecessor’s next to the new node and increase the list size.

For example, inserting 99 at position 2:

Before: dummy -> 1 -> 2 -> 3 -> None
After:  dummy -> 1 -> 99 -> 2 -> 3 -> None

Ignoring the dummy node, the logical states are:

Before: 1 -> 2 -> 3 -> None
After:  1 -> 99 -> 2 -> 3 -> None

Complexity

The pointer update itself is always O(1) because it changes a fixed number of links. Finding the insertion position requires traversal.

Case Time Reason
Best O(1) Inserting at position 1 requires no traversal
Average O(n) A typical position lies near the middle of the list
Worst O(n) The predecessor is near the end of the list

The auxiliary space complexity is O(1): only a fixed number of node references are used, and the recursion stack is also O(1) because the implementation is iterative. The linked list being modified is the input and is not counted as auxiliary space.

Compared with an array:

Operation Array Singly linked list
Access by index O(1) O(n)
Locate a position O(1) O(n)
Insert at a known index/node O(n) due to shifting O(1) after finding the predecessor
Delete at a known index/node O(n) due to shifting O(1) after finding the predecessor

Code Example

from __future__ import annotations


class ListNode:
    def __init__(self, val: int, next: ListNode | None = None) -> None:
        self.val = val
        self.next = next


class LinkedList:
    def __init__(self) -> None:
        # Dummy sentinel; its value is never counted as list data.
        self.head = ListNode(0)
        self.size = 0

    def insert_at(self, position: int, value: int) -> None:
        """Insert value at a 1-based data-node position."""
        if position < 1 or position > self.size + 1:
            raise IndexError("Position must be between 1 and size + 1")

        current = self.head
        slow = self.head
        fast = self.head

        for _ in range(position - 1):
            if current.next is None:
                raise IndexError("Position exceeds the list length")

            current = current.next

            # Floyd's pointers detect a cycle if traversal enters one.
            assert slow.next is not None
            slow = slow.next
            if fast is not None and fast.next is not None:
                fast = fast.next.next
            else:
                fast = None

            if slow is fast:
                raise ValueError("Cannot locate a position in a cyclic list")

        new_node = ListNode(value, current.next)
        current.next = new_node
        self.size += 1

    def to_values(self) -> list[int]:
        """Return the list's data-node values."""
        values: list[int] = []
        current = self.head.next

        while current is not None:
            values.append(current.val)
            current = current.next

        return values


linked_list = LinkedList()
linked_list.insert_at(1, 1)
linked_list.insert_at(2, 2)
linked_list.insert_at(3, 3)
linked_list.insert_at(2, 99)

print(linked_list.to_values())  # [1, 99, 2, 3]

Common Pitfalls

  • Position convention: Confirm whether the interviewer expects 0-based or 1-based indexing and whether insertion occurs before or after the specified node.

  • Empty list: Only position 1 is valid; the dummy head allows insertion without replacing head.

  • One element: Inserting at position 1 places the new node before it, while position 2 places it after it.

  • Duplicates and negative values: These are valid node values and do not affect insertion.

  • Sorted input: No special handling is needed because linked-list insertion preserves insertion order rather than numerical order.

  • Cycles: Normal position-based insertion assumes an acyclic list. The fast and slow pointers prevent traversal from becoming trapped when a cycle is encountered.

  • Interview follow-up: Candidates are often asked about zero-based indexing, appending at the tail, deleting by position, reversing the list, and detecting cycles with Floyd’s algorithm.

24

How do you delete a linked-list node without the head pointer?

Copy-and-bypass deletion removes a non-tail node from a singly linked list in O(1) time using only a reference to that node. You copy the next node’s value into the given node, then bypass and effectively delete the next node.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

Given a reference to node:

  1. Access its successor, node.next.

  2. Copy successor.val into node.val.

  3. Set node.next = successor.next, removing the successor from the list.

The original node object remains in the list, but it now represents the deleted value. This works because the caller cannot reach the predecessor needed to unlink the given node directly.

Operation Singly linked list Array
Access by index or position O(n) O(1)
Insert or delete at a known location O(1) when the predecessor/next link is known O(n) because elements must be shifted

Constraints and Edge Cases

  • Tail node: It cannot be deleted using this technique because it has no successor whose value can be copied. A one-element list is therefore also a tail case. Without a head pointer or predecessor, deletion is impossible.

  • First node: The method works from the list’s logical-value perspective, although the original first-node object remains in place.

  • Empty or missing input: The function should reject a None node.

  • Duplicates and negative values: These have no effect on the operation.

  • Sorted input: Ordering does not matter.

  • Cycles: The technique assumes a finite, acyclic singly linked list. Cycle detection would require additional traversal and change the complexity.

  • Doubly linked list: If each node maintains prev, the exact node can be unlinked without the head when its predecessor is available: update node.prev.next = node.next and, if node.next is not None, update node.next.prev = node.prev. A first node without a predecessor still requires a dummy or head pointer.

State Walkthrough

For the list:

dummy -> 1 -> 2 -> 3 -> None

The node containing 2 is the target. Its successor contains 3:

  1. Copy 3 into the target node.

  2. Bypass the old node containing 3.

The result is:

dummy -> 1 -> 3 -> None

The target node now contains 3, and the original successor has been removed.

Code Example

from __future__ import annotations

from dataclasses import dataclass


@dataclass(slots=True)
class ListNode:
    val: int
    next: ListNode | None = None


def delete_node_without_head(node: ListNode | None) -> None:
    """Delete a non-tail linked-list node without receiving the head."""
    if node is None:
        raise ValueError("Cannot delete a missing node.")

    successor = node.next
    if successor is None:
        raise ValueError("Cannot delete the tail without a head or predecessor.")

    node.val = successor.val
    node.next = successor.next


# A sentinel gives the surrounding list a stable starting point.
dummy = ListNode(0)
dummy.next = ListNode(1)
dummy.next.next = ListNode(2)
dummy.next.next.next = ListNode(3)

# Only the target node is passed; the operation does not use dummy.
delete_node_without_head(dummy.next.next)

current = dummy.next
while current is not None:
    print(current.val, end=" -> ")
    current = current.next
print("None")  # Expected output: 1 -> 3 -> None

Complexity

  • Best case: O(1) time, because a fixed number of values and pointers are updated.

  • Average case: O(1) time, with the same constant number of operations.

  • Worst case: O(1) time, assuming the node is not the tail.

  • Auxiliary space: O(1), including the constant number of local references. The input list is not counted, and no recursion stack is used.

Common Pitfalls

  • Confusing value deletion with object deletion: The given node remains; its successor is physically bypassed.

  • Attempting to delete the tail: Without a predecessor or head pointer, there is no safe way to perform this operation.

  • Assuming a sentinel solves the no-head constraint: A dummy head simplifies operations in the surrounding list implementation, but it cannot provide access to a predecessor when none was supplied.

  • Ignoring object identity: If the caller must remove the exact node object rather than merely delete its value, use a doubly linked list with prev pointers or obtain the predecessor.

25

How do you append a node to a linked list?

Appending a node to a singly linked list means connecting the current tail to the new node and ensuring the new node’s next pointer is None. Without a stored tail reference, finding the end requires a traversal.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Approach

Use a dummy head sentinel as the traversal starting point. It simplifies empty-list handling because the same traversal logic works whether the actual list is empty or nonempty.

For this list:

1 -> 2 -> 3 -> None

the operation proceeds as follows:

Step Dummy-head and tail state
Start D -> 1 -> 2 -> 3 -> None, with tail = D
Visit 1 Move tail to the node containing 1
Visit 2 Move tail to the node containing 2
Visit 3 Move tail to the node containing 3
Link Set 3.next to the new node containing 4
Return Return D.next, which points to the actual head

The resulting list is:

1 -> 2 -> 3 -> 4 -> None

The appended node must have next is None, and the function also rejects a node already reachable in the target list. A node cannot reveal whether it is the sole head of an unrelated list, so that broader provenance cannot be verified.

Edge Cases

  • Empty list: The dummy head becomes the predecessor of the only node.

  • One-element list: The traversal reaches the existing node and links the new node after it.

  • Duplicate or negative values: Values do not affect appending; nodes are compared by identity, not by val.

  • Already sorted input: Appending still places the node at the tail, but it does not necessarily preserve sorted order.

  • Cyclic input: A cyclic list has no well-defined tail, so the implementation detects the cycle and raises ValueError.

Complexity

Let n be the number of nodes before appending.

  • Best case: O(1) when the list is empty.

  • Average case: O(n), because validation and traversal examine the list.

  • Worst case: O(n), including cycle detection and finding the tail.

  • Auxiliary space: O(1) for the dummy node and Floyd’s slow/fast pointers. The input list and appended node are not counted as auxiliary space.

With a maintained tail pointer, appending and updating that pointer take O(1) best, average, and worst-case time.

Linked Lists Compared with Arrays

Operation Singly Linked List Dynamic Array
Access by index O(n) O(1)
Insert after a known node O(1) O(n) because elements shift
Delete after a known predecessor O(1) O(n) because elements shift
Append without a cached tail O(n) O(1) amortized; O(n) worst case during resizing
Additional space for the operation O(1) O(1) amortized; O(n) worst case during resizing

Code Example

from __future__ import annotations


class ListNode:
    def __init__(self, val: int, next_node: ListNode | None = None) -> None:
        self.val = val
        self.next = next_node


def append_node(head: ListNode | None, node: ListNode) -> ListNode | None:
    """Append a node whose next is None; reject cycles and reused nodes."""
    if node.next is not None:
        raise ValueError("The appended node must have next set to None.")

    # Floyd's algorithm detects a cyclic target without a visited set.
    slow = head
    fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            raise ValueError("Cannot append to a cyclic linked list.")

    # A dummy head gives empty and nonempty lists the same traversal logic.
    dummy_head = ListNode(0, head)
    tail = dummy_head

    while tail.next is not None:
        current = tail.next
        if current is node:
            raise ValueError("The appended node already belongs to the list.")
        tail = current

    tail.next = node
    return dummy_head.next


head = ListNode(1, ListNode(2, ListNode(3)))
head = append_node(head, ListNode(4))

values: list[int] = []
current = head
while current is not None:
    values.append(current.val)
    current = current.next

print(values)  # [1, 2, 3, 4]

Common Pitfalls

  • Returning the dummy head: Return dummy_head.next so callers receive the actual head.

  • Reusing an existing node: A node already in the target list cannot be appended again.

  • Mutating the input: Appending intentionally changes the target list; clone it first if the original must remain unchanged.

  • Integer overflow: Python integers do not overflow, but fixed-width languages must ensure the node value fits the allowed range.

  • Typical follow-up: Interviewers may ask how to maintain a tail pointer for O(1) appends or how to prepend and delete nodes.

26

How do you insert into a sorted singly linked list?

Use sorted insertion by traversing until the next node has a value greater than the new item, then linking the new node into that position. A dummy head simplifies insertion before the original first node and eliminates special-case pointer updates.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

For a list sorted in non-decreasing order:

  1. Create a dummy head whose next points to the original head.

  2. Maintain previous and current pointers.

  3. Advance while current.val <= value.

  4. Insert a new node between previous and current.

  5. Return dummy.next as the new head.

The implementation inserts duplicates after existing equal values. To insert each duplicate before existing equal values, change the loop condition from current.val <= value to current.val < value.

The dummy head is not part of the logical list; it only makes head insertion work without separate logic.

Complexity

Case Time Reason
Best O(1) The item is inserted before the first node, or the list is empty.
Average O(n) On average, the traversal visits roughly half the nodes.
Worst O(n) Every existing node is visited before the insertion point.
  • Auxiliary space: O(1) because only a dummy node, one new node, and a constant number of pointers are used.

  • The input list is not counted, and there is no recursive call stack.

Finding the correct position takes O(n), while linking the new node into an already known position takes O(1).

Linked List Versus Array

Operation Singly Linked List Array
Access by index O(n) O(1)
Search by value O(n) O(n)
Insert after a known node O(1) Not directly applicable
Insert at a known index O(n) to find the node O(n) to shift elements
Delete after a known node O(1) O(n) to shift elements
Insert/delete at the front O(1) O(n) for an array

Example Walkthrough

Before inserting 3:

1 -> 2 -> 4 -> None

  1. Visit 1; 1 <= 3, so advance.

  2. Visit 2; 2 <= 3, so advance.

  3. Reach 4; 4 > 3, so stop.

  4. Insert 3 between 2 and 4.

After insertion:

1 -> 2 -> 3 -> 4 -> None

Code Example

from __future__ import annotations

from dataclasses import dataclass


@dataclass(slots=True)
class ListNode:
    val: int
    next: ListNode | None = None


def insert_sorted(head: ListNode | None, value: int) -> ListNode:
    """Insert value into a non-decreasing singly linked list."""
    dummy = ListNode(0)
    dummy.next = head

    previous = dummy
    current = head

    # Insert after existing equal values.
    while current is not None and current.val <= value:
        previous = current
        current = current.next

    # Link the new node between previous and current.
    previous.next = ListNode(value, current)
    return dummy.next


def list_values(head: ListNode | None) -> list[int]:
    """Return the values stored in a singly linked list."""
    values: list[int] = []
    current = head

    while current is not None:
        values.append(current.val)
        current = current.next

    return values


head = ListNode(1, ListNode(2, ListNode(4)))
head = insert_sorted(head, 3)
print(list_values(head))  # [1, 2, 3, 4]

Common Pitfalls

  • Unsorted input: The algorithm assumes the list is already sorted; otherwise, the result may still be unsorted.

  • Duplicate policy: Decide whether equal values belong before or after existing equal values.

  • Lost links: Save current before assigning previous.next; otherwise, the remaining list can become unreachable.

  • Empty list: The dummy-head approach correctly returns a one-node list.

  • One element or negative values: These require no special handling because comparisons use ordinary numeric ordering.

  • Cycles: A cyclic list violates the acyclic-list assumption and can cause an infinite traversal.

  • Disconnected graphs: Not applicable to singly linked-list insertion.

  • Mutating the caller’s head: The function returns the possibly updated head, so callers must use that return value.

27

How does Floyd’s cycle detection algorithm find linked list cycles?

Floyd’s Cycle Detection Algorithm determines whether a linked list contains a cycle by advancing two pointers at different speeds. If they meet at the same node, the list contains a cycle; otherwise, the faster pointer reaches the end.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

  • Slow pointer: advances by one node per iteration.

  • Fast pointer: advances by two nodes per iteration.

  • Meeting condition: if both pointers reference the same node after moving, a cycle exists.

  • No-cycle condition: if the fast pointer reaches None, the list is finite and acyclic.

  • Dummy head: a sentinel node simplifies handling of an empty list and gives both pointers a consistent starting point. It does not modify the original list.

Node identity is checked with is, not by comparing val. A list containing duplicate values can still contain a cycle, and negative values have no effect on detection.

State Walkthrough

Consider the cyclic list:

1 -> 2 -> 3 -> 2 -> 3 -> ...

The pointer states are:

Iteration Slow pointer Fast pointer Result
Initially Dummy head Dummy head Continue
1 Node 1 Node 2 Different nodes
2 Node 2 Node 2 Cycle detected

The operation does not change the list:

Before: 1 -> 2 -> 3 -> 2 -> 3 -> ...
After:  1 -> 2 -> 3 -> 2 -> 3 -> ...

Inside a cycle, the fast pointer gains one node on the slow pointer per iteration. Therefore, their separation eventually becomes a multiple of the cycle length, causing them to meet.

Complexity

Let n be the number of distinct nodes before a node repeats.

  • Best case: O(1) time when the pointers meet immediately, such as a self-cyclic head node.

  • Average case: O(n) time because the pointers traverse at most a constant number of the list’s nodes.

  • Worst case: O(n) time because each pointer visits only a constant number of nodes per iteration.

  • Auxiliary space: O(1). Only a fixed number of pointers and one sentinel are used; there is no recursion stack. The input list itself occupies O(n) space if input storage is included.

Approach Time Auxiliary space When to use
Hash set of visited nodes O(n) expected O(n) When the cycle’s entry node is also required
Floyd’s algorithm O(n) O(1) Preferred for constant-space cycle detection

Code Example

from __future__ import annotations


class ListNode:
    def __init__(
        self,
        val: int,
        next: ListNode | None = None,
    ) -> None:
        self.val = val
        self.next = next


def has_cycle(head: ListNode | None) -> bool:
    """Return True if the linked list contains a cycle."""
    # A sentinel simplifies empty-list and head-node handling.
    dummy = ListNode(0, head)

    slow: ListNode | None = dummy
    fast: ListNode | None = dummy

    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next

        # Compare node identity, not stored values.
        if slow is fast:
            return True

    return False


# Example: 1 -> 2 -> 3 -> 2, where the cycle starts at node 2.
head = ListNode(1)
second = ListNode(2)
third = ListNode(3)
head.next = second
second.next = third
third.next = second

print(has_cycle(head))  # True

Linked Lists vs Arrays

Operation Linked list Array
Access by position O(n) O(1)
Insert after a known node O(1) O(n) due to shifting
Delete a known node and its predecessor O(1) O(n) due to shifting
Cycle detection with Floyd’s algorithm O(n) time, O(1) space Not directly applicable

Interview Tips

  • Empty list: the dummy head points to None, so the algorithm returns False.

  • Single node without a cycle: returns False.

  • Single node pointing to itself: the pointers meet, so it returns True.

  • Duplicate or negative values: irrelevant; detection uses node references.

  • Common mistake: comparing slow.val == fast.val instead of slow is fast.

  • Common follow-up: finding the cycle’s entry node by resetting one pointer to the head and moving both pointers one step at a time until they meet.

28

Which linked-list cycle detection algorithms improve on Floyd’s?

Floyd’s algorithm is already asymptotically optimal for cycle detection in a singly linked list: it uses O(n) time and O(1) extra space. Brent’s algorithm is a useful alternative with the same asymptotic complexity and often better constant factors because it moves only one pointer at a time.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Complexity and Alternatives

Algorithm Best time Typical time Worst time Extra space Reason
Floyd’s algorithm O(1) O(n) O(n) O(1) Two pointers advance at different speeds until they meet or the list ends.
Brent’s algorithm O(1) O(n) O(n) O(1) A checkpoint is periodically moved forward while one pointer traverses the list.
Hash-set approach O(1) O(n) expected O(n²) with pathological collisions O(n) Stores every visited node, using linear auxiliary memory.

There is no general O(log n) or O(1)-time replacement for Floyd’s algorithm on an ordinary linked list. In the worst case, an algorithm must inspect all n nodes to prove that a list is cycle-free; otherwise, an unseen node could still point back into the path already traversed.

Brent’s algorithm can be preferable when pointer-update overhead matters, but it does not improve the asymptotic time or space bounds.

How Floyd’s Algorithm Works

Floyd uses a fast pointer and a slow pointer:

  1. Initialize both pointers at the head.

  2. Move slow forward by one node and fast forward by two nodes.

  3. If the pointers meet, the list contains a cycle.

  4. If fast reaches None, the list is acyclic.

If a cycle exists, the fast pointer gains one position per round on the slow pointer. Their separation within the cycle eventually becomes zero, so they must meet.

The algorithm returns a node somewhere in the cycle, not necessarily the cycle’s entry node. Finding the entry node requires an additional phase.

Edge Cases

  • Empty list: head is None; return None.

  • One-element list without a self-loop: the fast pointer reaches None; return None.

  • Self-loop: the node’s next points to itself; detect the cycle.

  • Duplicate values: detection compares node identity, not val, so repeated values do not affect correctness.

  • Negative values: values are irrelevant to cycle detection.

  • Already sorted values: sorting has no effect; linked-list cycle detection does not require ordered data.

  • Disconnected graphs: not applicable to a singly linked list, which has one traversal path.

  • Multiple cycles: impossible in a standard singly linked list reachable from one head; each node has only one next pointer.

Common Pitfalls

  • Comparing slow.val == fast.val instead of slow is fast can produce false positives when values are duplicated.

  • Returning the meeting node and assuming it is the cycle entry is incorrect.

  • Forgetting the fast is not None and fast.next is not None checks can cause an AttributeError.

  • A hash-set solution uses O(n) extra space and is generally inferior to Floyd’s or Brent’s algorithm when memory matters.

  • In interviews, the useful follow-up is: “Can you find the cycle’s entry node?” or “Can you compute the cycle’s length?”

29

How do you uniformly shuffle a linked list?

A uniform shuffle randomly reorders a linked list so that every permutation of its nodes is equally likely. The Fisher–Yates algorithm provides this guarantee, while a dummy head node simplifies reconnecting the shuffled nodes.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

  1. Detect cycles with Floyd’s fast and slow pointers so traversal cannot loop forever.

  2. Collect references to all nodes in an array.

  3. Apply Fisher–Yates in reverse order:

  4. For each index i, choose a random index j from 0 through i.

  5. Swap nodes at positions i and j.

  6. Reconnect the shuffled nodes using a dummy head node and return dummy.next.

The dummy node removes special cases around the first node. It also gives the function a stable return point even when the shuffled head changes.

Fisher–Yates is uniform because each step selects one remaining node uniformly at random. By induction, all n! permutations have probability 1 / n!.

Example Walkthrough

Starting state:

1 -> 2 -> 3 -> 4 -> None

With random.Random(0), Fisher–Yates selects indices 3, 1, and 1:

Step 1: 1 -> 2 -> 3 -> 4 -> None
Step 2: 1 -> 3 -> 2 -> 4 -> None
Step 3: 1 -> 3 -> 2 -> 4 -> None

The nodes are reused; their values and object identities are not copied.

Complexity

For n nodes:

Measure Best Average Worst Reason
Time O(n) O(n) O(n) Cycle detection, collection, shuffling, and reconnection each visit a constant number of nodes per element
Auxiliary space O(n) O(n) O(n) The node-reference array contains n elements
Recursion stack O(1) O(1) O(1) The implementation is fully iterative

The auxiliary-space figure excludes the input nodes because they are reused and mutated. Including the input list’s storage, total space remains O(n).

Linked Lists vs Arrays

Operation Array Singly linked list
Access by index O(1) O(n)
Insert or delete at a known index O(n) O(n) to locate the position
Insert or delete after a known node O(n) due to shifting O(1)
Uniform shuffle used here O(n) time, O(n) auxiliary space O(n) time, O(n) auxiliary space

Code Example

from __future__ import annotations

import random


class ListNode:
    def __init__(self, val: int, next: ListNode | None = None) -> None:
        self.val = val
        self.next = next


def shuffle_linked_list(
    head: ListNode | None,
    rng: random.Random | None = None,
) -> ListNode | None:
    """Uniformly reorder the existing nodes in place and return the new head."""
    if head is None:
        return None

    # Floyd's algorithm: reject cyclic lists before traversing them.
    slow = head
    fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            raise ValueError("Cannot shuffle a linked list containing a cycle")

    generator = rng if rng is not None else random.Random()

    # Collect node references without copying their values.
    nodes: list[ListNode] = []
    current = head
    while current is not None:
        nodes.append(current)
        current = current.next

    # Fisher-Yates: choose a uniform random index at each step.
    for index in range(len(nodes) - 1, 0, -1):
        swap_index = generator.randrange(index + 1)
        nodes[index], nodes[swap_index] = nodes[swap_index], nodes[index]

    # Reconnect the shuffled nodes using a dummy head.
    dummy = ListNode(0)
    tail = dummy
    for node in nodes:
        tail.next = node
        tail = node
    tail.next = None

    return dummy.next


def linked_list_values(head: ListNode | None) -> list[int]:
    """Return the values stored in a linked list."""
    values: list[int] = []
    current = head
    while current is not None:
        values.append(current.val)
        current = current.next
    return values


head = ListNode(1, ListNode(2, ListNode(3, ListNode(4))))
shuffled = shuffle_linked_list(head, random.Random(0))
print(linked_list_values(shuffled))
# Expected output: [1, 3, 2, 4]

Common Pitfalls

  • Uniformity: Repeatedly swapping two random positions independently is not equivalent to Fisher–Yates and can produce biased permutations.

  • Off-by-one errors: The random index must be between 0 and i, inclusive.

  • Cycles: A cyclic list would make traversal infinite; the implementation detects it with Floyd’s algorithm.

  • Mutation: This algorithm reorders the original nodes and changes their next pointers. Clone the nodes first if the input must remain unchanged.

  • Edge cases: Empty and one-node lists are handled; duplicates, negative values, and already sorted inputs require no special logic. Disconnected lists are outside the operation’s scope.

  • Interview follow-up: Discuss whether the shuffle must be uniform, whether nodes may be copied, how the new head is tracked, and how cycles are detected.

30

How can a hash table detect cycles in a linked list?

A hash table detects a cycle by recording each visited node. If the traversal encounters the same node again, the list contains a cycle; reaching None means the list is acyclic.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

  1. Create a dummy ListNode whose next pointer references the original head.

  2. Traverse the list using the dummy node as a stable starting point.

  3. Store every visited node in a set.

  4. Return True when a node is already in the set.

  5. Return False when traversal reaches None.

The set stores node objects, not node values. Consequently, repeated values such as two different nodes containing 2 do not incorrectly indicate a cycle.

Example Walkthrough

For this cyclic list:

Before: dummy -> 1 -> 2 -> 3 -> 1
Step Current node Already visited Result
1 1 No Add 1 and continue
2 2 No Add 2 and continue
3 3 No Add 3 and continue
4 1 Yes Cycle detected

The operation does not modify the list:

After:  dummy -> 1 -> 2 -> 3 -> 1

For an acyclic list, traversal follows dummy -> 1 -> 2 -> None and returns False.

Complexity

Let n be the number of distinct nodes reachable from the head.

  • Best time: O(1), such as for an empty list or a one-node self-cycle.

  • Average time: O(n) expected, because each node is processed once and hash-set membership takes O(1) on average.

  • Worst time: O(n²) in a theoretical hash-collision scenario where each membership check takes O(n). Interview solutions normally report the expected O(n) bound.

  • Auxiliary space: O(n) for the visited set, excluding the input list. The dummy node uses O(1) space, and no recursion stack is used.

Linked List vs Array

Operation Linked list Array
Access by index O(n) O(1)
Insert or delete at a known location O(1) with the predecessor O(n) due to shifting
Cycle detection with visited nodes O(n) space O(n) space

Code Example

from __future__ import annotations


class ListNode:
    __slots__ = ("val", "next")

    def __init__(self, val: int, next: ListNode | None = None) -> None:
        self.val = val
        self.next = next


def has_cycle(head: ListNode | None) -> bool:
    """Return whether the linked list contains a cycle."""
    # A dummy head gives traversal a consistent starting point.
    dummy = ListNode(0, head)
    visited: set[ListNode] = set()
    current = dummy.next

    while current is not None:
        # ListNode uses identity-based equality and hashing.
        if current in visited:
            return True

        visited.add(current)
        current = current.next

    return False


first = ListNode(1)
second = ListNode(2)
third = ListNode(3)
first.next = second
second.next = third
third.next = first

print(has_cycle(first))  # True

Common Pitfalls

  • Storing values instead of nodes: A cycle means revisiting the same object, not merely encountering equal values.

  • Forgetting the None check: Attempting to access None.next causes an error.

  • Treating the dummy node as evidence of a cycle: The dummy node is only a traversal helper and is not revisited.

  • Mutating the list: This algorithm should only read next pointers.

  • Interview follow-up: Floyd’s fast-and-slow-pointer algorithm also detects a cycle in O(n) time but uses only O(1) auxiliary space.

31

How do you implement sorting for a linked list?

Use merge sort to sort a linked list in ascending order by val. It repeatedly combines small, sorted sublists into larger sorted sublists, making it stable and suitable for linked lists because it does not require random-access indexing.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Approach

The implementation uses bottom-up merge sort:

  1. Compute the length of the list.

  2. Start with runs of one node.

  3. Merge adjacent sorted runs into runs of double the size.

  4. Double the run size and repeat until the run size exceeds the list length.

  5. Use a dummy head so the first merged segment can be attached without special-case logic.

The dummy head simplifies pointer updates at the beginning of the list, while a temporary dummy node inside each merge simplifies appending nodes to the merged result.

For example:

  • Before: 4 -> 1 -> 3 -> 2 -> None

  • After: 1 -> 2 -> 3 -> 4 -> None

The implementation reuses the original nodes, so it mutates the list in place and returns the new head.

Linked List vs Array

Operation Linked List Array
Access by index O(n) O(1)
Insert/delete at known node O(1) O(n)
Memory overhead O(n) extra for pointers Contiguous, no overhead
Cache locality Poor Excellent

Approach Comparison

Approach Time Auxiliary Space When to Use
Repeatedly find and move the minimum O(n²) best, average, and worst O(1) Simple educational implementation
Bottom-up merge sort O(n log n) best, average, and worst O(1) Efficient general-purpose sorting
Top-down merge sort O(n log n) best, average, and worst O(log n) recursion stack Clearer recursive implementation

How It Works

  • Split: _split separates a list after a specified number of nodes and returns the head of the first part and the head of the remainder.

  • Merge: _merge combines two sorted lists by repeatedly selecting the smaller val and returns the head and tail of the merged list.

  • Stability: The comparison uses <=, so nodes with equal values retain their original relative order.

  • Iterative design: Bottom-up merging avoids recursion-depth issues for lists containing more than roughly 1,000 nodes.

Complexity

  • Time: O(n log n) in the best, average, and worst cases. Each of the O(log n) merge passes processes O(n) nodes.

  • Auxiliary space: O(1), excluding the input list. The algorithm uses no recursion stack and creates only temporary dummy nodes.

  • Total storage: O(n), because the existing input nodes are reused as the output list.

Code Example

from __future__ import annotations


class ListNode:
    def __init__(self, val: int, next: ListNode | None = None) -> None:
        self.val = val
        self.next = next


def _split(
    head: ListNode | None,
    size: int,
) -> tuple[ListNode | None, ListNode | None]:
    """Split a list into its first `size` nodes and the remainder."""
    if head is None:
        return None, None

    last = head
    for _ in range(size - 1):
        if last.next is None:
            return head, None
        last = last.next

    remainder = last.next
    last.next = None
    return head, remainder


def _merge(
    left: ListNode | None,
    right: ListNode | None,
) -> tuple[ListNode | None, ListNode]:
    """Merge two sorted linked lists and return their head and tail."""
    dummy_head = ListNode(0)
    tail = dummy_head

    while left is not None or right is not None:
        if right is None or (
            left is not None and left.val <= right.val
        ):
            chosen = left
            left = left.next
        else:
            chosen = right
            right = right.next

        tail.next = chosen
        tail = chosen

    tail.next = None
    return dummy_head.next, tail


def sort_linked_list(head: ListNode | None) -> ListNode | None:
    """Sort a linked list in ascending order using bottom-up merge sort."""
    if head is None or head.next is None:
        return head

    # Compute length of the list
    length = 0
    node = head
    while node:
        length += 1
        node = node.next

    dummy_head = ListNode(0)
    dummy_head.next = head
    run_size = 1

    while run_size < length:
        prev = dummy_head
        curr = dummy_head.next

        while curr:
            left, rest = _split(curr, run_size)
            right, curr = _split(rest, run_size)
            merged_head, merged_tail = _merge(left, right)
            prev.next = merged_head
            prev = merged_tail

        run_size *= 2

    return dummy_head.next


if __name__ == "__main__":
    example = sort_linked_list(
        ListNode(4, ListNode(1, ListNode(3, ListNode(2))))
    )

    values = []
    current = example
    while current is not None:
        values.append(current.val)
        current = current.next

    print(values)
    # Expected output: [1, 2, 3, 4]

Common Pitfalls

  • Empty list: sort_linked_list(None) returns None.

  • Single element: The value is returned unchanged.

  • Duplicate values: Stable sorting preserves their original order.

  • Negative values: Numeric comparison handles them normally.

  • Already sorted input: The result remains sorted, with the same O(n log n) worst-case time.

  • Cycles: A cyclic list is unsupported and can cause nontermination; use Floyd’s cycle-detection algorithm before sorting if the input is not guaranteed to be acyclic.

  • Pointer updates: Forgetting to advance prev to the merged tail or curr to the next remaining segment is a common error.

  • Stability: Using < instead of <= can reverse the relative order of equal-valued nodes.

Interview Tips

Explain why merge sort is preferred over repeatedly finding the minimum, then state that the implementation uses iterative bottom-up merging to avoid recursion-depth limits. Interviewers may follow up about detecting cycles, sorting in descending order, or modifying the algorithm to sort by a custom key.

32

How do you merge two sorted singly linked lists by reusing nodes?

In-place merging combines two ascending linked lists by rewiring their existing next pointers, so the result reuses the original ListNode objects without allocating new payload nodes. A temporary dummy sentinel simplifies the first-node and empty-list cases.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Idea

Maintain a pointer to the smallest unmerged node in each list and another pointer, tail, to the end of the merged result:

  • Compare the two current values.

  • Append the smaller node by updating tail.next.

  • Advance only the pointer belonging to the list from which the node came.

  • When one list is exhausted, attach the remainder of the other list directly.

Using <= when values are equal preserves stability: equal elements from the left list appear before equal elements from the right list.

The dummy sentinel avoids separate logic for inserting the first element. It is temporary and is not part of the returned list.

Walkthrough

Given:

Left:  1 -> 2 -> 4 -> None
Right: 2 -> 3 -> 5 -> None

The merge proceeds as follows:

  1. Take 1 from the left list.

  2. Take 2 from the left list because 2 <= 2.

  3. Take 2 from the right list.

  4. Take 3 from the right list.

  5. Take 4 from the left list.

  6. Attach the remaining 5 from the right list.

Result:

1 -> 2 -> 2 -> 3 -> 4 -> 5 -> None

Every result node is an original node; only its next pointer may have changed.

Complexity

Let n and m be the lengths of the two lists.

Case Time Reason
Best O(n + m) Cycle validation and merging are linear; an empty input pair takes O(1)
Average O(n + m) Each list is traversed a constant number of times
Worst O(n + m) Each original node is examined a constant number of times

Auxiliary space: O(1), including cycle-detection variables and the temporary sentinel. The input nodes are not counted because they are reused, and there is no recursion stack.

Linked Lists vs Arrays

Operation Singly linked list Array
Access by index O(n) O(1)
Insert or delete after a known node O(1) O(n), because elements may shift
Merge two sorted collections O(n + m) O(n + m), including copying or shifting

Code Example

from __future__ import annotations


class ListNode:
    __slots__ = ("val", "next")

    def __init__(self, val: int, next: ListNode | None = None) -> None:
        self.val = val
        self.next = next


def _has_cycle(head: ListNode | None) -> bool:
    """Detect a cycle with Floyd's fast and slow pointers."""
    slow = head
    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 merge_sorted_lists(
    left: ListNode | None,
    right: ListNode | None,
) -> ListNode | None:
    """Merge two ascending lists in place by reusing their nodes."""
    if _has_cycle(left) or _has_cycle(right):
        raise ValueError("Input linked lists must not contain cycles.")

    dummy = ListNode(0)
    tail = dummy

    while left is not None and right is not None:
        if left.val <= right.val:
            tail.next = left
            left = left.next
        else:
            tail.next = right
            right = right.next

        tail = tail.next

    # Attach the remaining nodes without copying them.
    tail.next = left if left is not None else right

    return dummy.next


left = ListNode(1, ListNode(2, ListNode(4)))
right = ListNode(2, ListNode(3, ListNode(5)))

merged = merge_sorted_lists(left, right)

values: list[int] = []
current = merged
while current is not None:
    values.append(current.val)
    current = current.next

print(*values)
# Expected output: 1 2 2 3 4 5

Common Pitfalls

  • Mutating the input: Both original lists are modified. Their nodes must not be reused independently afterward.

  • Forgetting the remainder: After one list ends, the remaining list must be attached; otherwise nodes are lost.

  • Duplicate handling: Using <= keeps the merge stable. Using < gives priority to the right list instead.

  • Cycles: A cyclic input violates the linked-list ordering assumptions and can cause an infinite loop. The implementation rejects cycles using Floyd’s algorithm.

  • Edge cases: Empty lists return the other list or None; one-element lists work unchanged; duplicates and negative values are handled by ordinary integer comparison. Already sorted inputs are valid and follow the same merge path without special handling. Disconnected graphs are not applicable to linked lists.

  • No-new-node requirement: The output contains no newly created payload nodes. The code allocates only one temporary dummy sentinel; if even that allocation is prohibited, use the first existing node as the initial anchor and handle the empty case separately.

  • Interview follow-ups: Common questions include cycle detection, reversing the merged list, extending the merge to k sorted lists, and explaining why the algorithm uses O(1) auxiliary space.

33

How do you reverse a linked list recursively in Python?

Recursive linked-list reversal changes each node’s next pointer so that it points to the previously visited node, making the original tail the new head. A dummy sentinel simplifies the implementation and keeps edge cases such as an empty list consistent.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

The recursive helper follows these steps:

  1. If the current node is None, return the previous node as the new head.

  2. Save the current node’s original next pointer.

  3. Point the current node backward to previous.

  4. Recursively reverse the remainder of the list.

The dummy sentinel acts as the initial previous node. After recursion, the original head is the tail, so its pointer is cleared and the dummy node points to the new head. The dummy node itself is not included in the returned list.

Code Example

from __future__ import annotations


class ListNode:
    def __init__(self, val: int, next_node: ListNode | None = None) -> None:
        self.val = val
        self.next = next_node


def reverse_linked_list_recursively(
    head: ListNode | None,
) -> ListNode | None:
    """Reverse a singly linked list in place and return its new head."""
    dummy = ListNode(0, head)
    original_head = head

    def reverse(
        current: ListNode | None,
        previous: ListNode | None,
    ) -> ListNode | None:
        if current is None:
            return previous

        next_node = current.next
        current.next = previous
        return reverse(next_node, current)

    new_head = reverse(head, dummy)

    # The original head is now the tail; remove the temporary sentinel link.
    if original_head is not None:
        original_head.next = None

    # Keep the dummy's next pointer aligned with the reversed list.
    dummy.next = new_head if new_head is not dummy else None
    return dummy.next


head = ListNode(1, ListNode(2, ListNode(3)))
reversed_head = reverse_linked_list_recursively(head)

values = []
current = reversed_head
while current is not None:
    values.append(current.val)
    current = current.next

print(values)  # Expected output: [3, 2, 1]

State Trace

For the list:

1 -> 2 -> 3 -> None

The recursion temporarily changes the pointers as it unwinds:

3 -> 2 -> 1 -> dummy

After removing the temporary sentinel link, the returned list is:

3 -> 2 -> 1 -> None

The operation modifies the existing nodes in place.

Complexity

  • Best case: O(n) time, because every node must be visited once.

  • Average case: O(n) time, because every node must be visited once.

  • Worst case: O(n) time, because every node must be visited once.

  • Auxiliary space: O(n) for the recursion stack. The input list’s existing O(n) nodes are not counted as auxiliary space.

Linked Lists Compared with Arrays

Operation Linked list Array
Access by position O(n) O(1)
Insert or delete at a known node O(1) O(n)
Insert or delete at the beginning O(1) O(n)
Reversal with constant extra storage O(n) using an iterative approach O(n)

Common Pitfalls

  • Empty list: The function returns None without errors.

  • One element: The node becomes both the head and tail, with next set to None.

  • Duplicate or negative values: Values are preserved; only links change.

  • Already sorted list: The order is simply reversed.

  • Lost next pointer: Save current.next before changing it.

  • Sentinel returned by mistake: Return dummy.next, not dummy.

  • Recursion depth: Lists longer than roughly 1,000 nodes may exceed Python’s default recursion limit. Use an iterative prev/current/next solution when very large lists are expected.

  • Cycles: Recursive reversal assumes a finite acyclic list. A cyclic list would recurse indefinitely without cycle detection.

  • Disconnected graphs: This operation applies to one linked list, so disconnected-graph handling is not applicable.

34

How do you reverse a linked list in groups of K nodes?

Reverse each consecutive group of K nodes in a singly linked list, leaving any remaining nodes unchanged. A dummy head node and a previous/current/next_node pointer pattern make group boundaries easy to handle, including when the list length is not divisible by K.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Approach

  1. Create a dummy node whose next pointer initially references the original head.

  2. Locate the end of the next group of K nodes.

  3. If fewer than K nodes remain, stop and leave that remainder unchanged.

  4. Reverse the group using previous, current, and next_node pointers.

  5. Connect the reversed group to the preceding and following nodes.

  6. Continue with the next group.

For example, with K = 2:

Before: 1 -> 2 -> 3 -> 4 -> 5 -> None
After:  2 -> 1 -> 4 -> 3 -> 5 -> None

The incomplete final group, 5, is not reversed.

Complexity

Operation Best case Average case Worst case Space
Reverse groups O(n) O(n) O(n) O(1) auxiliary
  • Time: O(n) because the algorithm traverses the list to locate group boundaries and reverses each node once.

  • Space: O(1) auxiliary space. The input list is modified in place, and no recursion stack is used. If the storage occupied by the input nodes is counted, total space is O(n).

  • If K <= 1, the function returns immediately in O(1) time.

Linked List vs. Array

Operation Singly linked list Array
Access by index O(n) O(1)
Search for a value O(n) O(n)
Insert or delete at a known node/index O(1) for a known linked-list node; O(n) to locate it O(n)
Reversal O(1) extra space O(1) extra space

Code Example

class ListNode:
    def __init__(self, val: int = 0, next: "ListNode | None" = None) -> None:
        self.val = val
        self.next = next


def reverse_k_group(head: ListNode | None, group_size: int) -> ListNode | None:
    """Reverse each complete group of group_size nodes in place."""
    if group_size <= 1:
        return head

    # The dummy head removes special cases for the first group.
    dummy = ListNode(0, head)
    group_previous = dummy

    while group_previous.next is not None:
        # Find the tail of the next complete group.
        group_tail = group_previous
        for _ in range(group_size):
            if group_tail.next is None:
                # Fewer than group_size nodes remain; leave them unchanged.
                return dummy.next
            group_tail = group_tail.next

        # Reverse the nodes from group_previous.next through group_tail.
        previous: ListNode | None = None
        current = group_previous.next

        while current is not group_tail.next:
            next_node = current.next
            current.next = previous
            previous = current
            current = next_node

        # Reconnect the reversed group to the rest of the list.
        group_previous.next = previous
        group_tail.next = current
        group_previous = group_tail

    return dummy.next


# Example call
head = ListNode(
    1,
    ListNode(2, ListNode(3, ListNode(4, ListNode(5))))
)
result = reverse_k_group(head, 2)

values = []
current = result
while current is not None:
    values.append(current.val)
    current = current.next

print(values)  # Expected output: [2, 1, 4, 3, 5]

Common Pitfalls and Interview Tips

  • Incorrectly reversing the remainder: If fewer than K nodes remain, do not reverse them; return the unchanged remainder.

  • Losing links: Save current.next before changing current.next, then reconnect the reversed group’s head and tail.

  • Forgetting the dummy node: A dummy head simplifies updates when the first group is reversed and eliminates a separate “new head” case.

  • Mutating the input: This algorithm modifies the existing list rather than creating new nodes. Mention this explicitly if the interviewer asks whether the input may be changed.

  • Edge cases: Empty and one-element lists work without modification. Duplicate, negative, or already sorted values do not affect the algorithm because only links are changed.

  • Cycles: The implementation assumes an acyclic singly linked list. A cyclic list should be detected separately, for example with Floyd’s fast-and-slow-pointer algorithm.

  • Typical follow-up: Explain how to reverse exactly K nodes, how to leave the remainder unchanged, or how to detect a cycle using fast and slow pointers.

35

How do you locate the N-th element from a linked list's end?

The two-pointer gap technique finds the N-th element from the end in one linear traversal after validation. Move a fast pointer N nodes ahead, then advance both pointers until the fast pointer reaches None; the slow pointer will identify the target.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

For a one-based position N:

  1. Reject non-positive N and detect whether the list contains a cycle.

  2. Create a dummy head node, ListNode(0, head), to provide a stable starting point without special-casing the first real node.

  3. Advance the fast pointer N nodes from the dummy node.

  4. Move both pointers forward until the fast pointer reaches None.

  5. The slow pointer now references the N-th element from the end.

If N exceeds the list length, the function raises ValueError. A cyclic list is also rejected because it has no well-defined end.

Step-by-Step Example

For N = 2:

Original: 10 -> 20 -> 30 -> 40 -> None
With dummy: 0 -> 10 -> 20 -> 30 -> 40 -> None
After lookup (target = 30): 10 -> 20 -> 30 -> 40 -> None
Step Slow pointer Fast pointer
After advancing fast 0 20
Move both 10 30
Move both 20 40
Move both 30 None

The slow pointer contains 30, which is the second element from the end.

Complexity

Let L be the number of nodes and N the requested position.

Case Time Reason
Best O(L) Cycle validation and pointer traversal inspect the list
Average O(L) The operation is deterministic for linked lists
Worst O(L) At most two linear passes are performed
  • Auxiliary space: O(1) for the dummy node and pointers.

  • Input storage: The input list is not counted.

  • Recursion stack: O(1) because the implementation is iterative.

Linked Lists vs Arrays

Operation Singly linked list Array
Access by index O(L) O(1)
Insert after a known node O(1) O(L) because elements shift
Delete a known node O(1) O(L) because elements shift
Find the N-th from the end O(L) O(L) unless the length is already known

Linked lists are therefore useful when frequent insertion or deletion after known nodes matters more than constant-time indexed access.

Code Example

from __future__ import annotations


class ListNode:
    def __init__(self, val: int, next: ListNode | None = None) -> None:
        self.val = val
        self.next = next


def find_nth_from_end(head: ListNode | None, n: int) -> int:
    """Return the value at the 1-based position n from the end."""
    if n <= 0:
        raise ValueError("n must be a positive integer")

    # Detect a cycle using Floyd's fast and slow pointers.
    slow = head
    fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            raise ValueError("A cyclic list has no well-defined end")

    # The dummy node simplifies handling the beginning of the list.
    dummy = ListNode(0, head)
    fast = dummy

    # Place the fast pointer n nodes ahead of the dummy node.
    for _ in range(n):
        if fast.next is None:
            raise ValueError("n exceeds the number of list elements")
        fast = fast.next

    # Maintain the gap until the fast pointer reaches the end.
    slow = dummy
    while fast is not None:
        slow = slow.next
        fast = fast.next

    assert slow is not None
    return slow.val


# Example: 10 -> 20 -> 30 -> 40 -> None
head = ListNode(10, ListNode(20, ListNode(30, ListNode(40))))
print(find_nth_from_end(head, 2))  # 30

Common Pitfalls and Interview Tips

  • Off-by-one errors: This implementation treats N = 1 as the last element. Zero and negative positions are invalid.

  • Empty list: Even N = 1 raises ValueError because the list has no last element.

  • Single-element list: N = 1 returns that element; larger values are rejected.

  • Duplicates: Duplicate values are supported because selection is based on position, not value.

  • Negative values: Negative element values are supported for the same reason.

  • Sorted input: Ordering is irrelevant; the algorithm works with sorted and unsorted values.

  • Cycles: Floyd’s algorithm detects a cycle before the gap traversal. A visited set is unnecessary.

  • Mutation: The function does not change links or values in the input list.

  • Integer overflow: Python integers have arbitrary precision; implementations in fixed-width languages must use overflow-safe arithmetic.

  • Common follow-up: A two-pass solution can first calculate the list length and then traverse to index L - N. The two-pointer solution uses constant auxiliary space without storing the length.

36

How do you remove duplicates from an unsorted linked list?

Use a hash set to track values already encountered while traversing the list. Keep the first occurrence of each value and unlink later duplicates, preserving the relative order of retained nodes.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

  • A dummy head node anchors the traversal and provides uniform pointer and empty-list handling. The function returns dummy_head.next, so the sentinel itself is never included in the result.

  • A set stores values already seen.

  • For each node:

  • If its value is new, add it to the set and advance the current pointer.

  • If its value is already present, bypass the duplicate with current.next = node.next.

  • Because only later occurrences are removed, the original head is retained under this keep-first-occurrence policy.

Complexity

Approach Best time Average time Worst time Extra space
Set-based traversal O(n) O(n) O(n²) O(k)
Compare every node with all previous nodes O(n²) O(n²) O(n²) O(1)

For the set-based approach:

  • Best case: O(n), because every node must be visited and no harmful hash collisions occur.

  • Average case: O(n), because set lookup and insertion take O(1) on average.

  • Worst case: O(n²), because severe hash collisions can make each set operation O(n).

  • Space: O(k), where k is the number of distinct values; this becomes O(n) in the worst case. The input list itself is not counted, and no recursion stack is used.

Compared with arrays:

Operation Linked list Array
Access by position O(n) O(1)
Insert/delete at a known node O(1) O(n)

Code Example

from __future__ import annotations


class ListNode:
    def __init__(self, val: int, next: ListNode | None = None) -> None:
        self.val = val
        self.next = next


def remove_duplicates(head: ListNode | None) -> ListNode | None:
    """Remove later duplicate values while preserving the first occurrence."""
    dummy_head = ListNode(0)
    dummy_head.next = head

    seen: set[int] = set()
    current = dummy_head

    while current.next is not None:
        node = current.next

        if node.val in seen:
            # Unlink the duplicate without changing the traversal order.
            current.next = node.next
        else:
            seen.add(node.val)
            current = node

    return dummy_head.next


head = ListNode(
    1,
    ListNode(
        2,
        ListNode(
            1,
            ListNode(3, ListNode(2)),
        ),
    ),
)

result = remove_duplicates(head)

values = []
current = result
while current is not None:
    values.append(current.val)
    current = current.next

print(values)  # [1, 2, 3]

Example Walkthrough

Before removal:

1 -> 2 -> 1 -> 3 -> 2 -> None
  1. Visit 1: it is new, so add it to seen.

  2. Visit 2: it is new, so add it to seen.

  3. Visit the second 1: it is a duplicate, so unlink it.

  4. Visit 3: it is new, so add it to seen.

  5. Visit the second 2: it is a duplicate, so unlink it.

After removal:

1 -> 2 -> 3 -> None

Common Pitfalls

  • Head handling: Return dummy_head.next, not dummy_head. The original head is retained under the keep-first-occurrence policy, but the sentinel keeps traversal logic uniform.

  • Advancing incorrectly: When a duplicate is removed, keep current in place. Advancing immediately would skip checking the next node and is the relevant pointer off-by-one error.

  • Failing to track seen values: Initialize seen for each call and add every retained value. Forgetting to do so allows duplicates to remain.

  • Unexpected mutation: The function modifies the list in place rather than creating a new list. Document this behavior in an interview.

  • Fixed-width integers: Python integers have arbitrary precision. In languages with fixed-width integers, choose a value type that can represent every permitted list value before applying the same algorithm.

  • Edge cases: It handles an empty list, a one-element list, duplicates, negative values, sorted or unsorted input, and an already duplicate-free list. It does not detect cycles, so the input must be acyclic.

  • Typical follow-up: Interviewers may ask how the solution would change if the last occurrence had to be retained, or how you would solve the problem if the list were guaranteed to be sorted.

37

How do you find common values in two linked lists?

Common elements are values that appear in both linked lists. The implementation below returns each matching value once, in the order it appears in the second list, using a new linked list.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

  1. Traverse the first list and store its values in a hash set.

  2. Traverse the second list.

  3. Add a value to the result when it exists in the first list and has not already been added to the result (the result order follows the second list).

  4. Use a dummy head node so appending nodes does not require special handling for the first result element.

The returned list contains only distinct common values. For example, if the first list contains 4 twice and the second list contains 4 twice, 4 appears only once in the result.

Example Walkthrough

Given:

List 1: 1 -> 4 -> 2 -> 3 -> None
List 2: 4 -> 2 -> 4 -> 3 -> None

The algorithm proceeds as follows:

  1. Store 1, 4, 2, and 3 from List 1 in a set.

  2. Read 4 from List 2: it exists in the first set, so append it.

  3. Read 2: it exists and is not yet in the result, so append it.

  4. Read the second 4: it is already in the result, so skip it.

  5. Read 3: it exists and is not yet in the result, so append it.

Result:

4 -> 2 -> 3 -> None

Complexity

Let n be the length of the first list, m the length of the second list, and k the number of distinct common values.

Case Time Reason
Best O(1) If either list is empty, the function returns immediately without traversal.
Average O(n + m) Both lists are traversed once and hash operations are O(1) on average.
Worst O(n(n + m)) Pathological hash collisions can make each set operation O(n).
  • Auxiliary space: O(n), excluding the input lists.

  • Output space: O(k), which is additional space if the returned list is counted separately.

  • The input lists are not modified.

Comparison with Arrays

Operation Linked List Array
Access by position O(n) O(1)
Insert after a known node O(1) O(n)
Delete after a known node O(1) O(n)
Search by value O(n) O(n) on average

Linked lists are useful when frequent insertion or deletion is required and random positional access is not important.

Code Example

from __future__ import annotations


class ListNode:
    def __init__(self, val: int, next: ListNode | None = None) -> None:
        self.val = val
        self.next = next


def common_elements(
    head1: ListNode | None,
    head2: ListNode | None,
) -> ListNode | None:
    """Return distinct values common to two acyclic linked lists."""
    if head1 is None or head2 is None:
        return None

    first_list_values: set[int] = set()
    current = head1

    while current is not None:
        first_list_values.add(current.val)
        current = current.next

    # The dummy head removes the need to handle the first result node separately.
    dummy_head = ListNode(0)
    tail = dummy_head
    added_values: set[int] = set()

    current = head2
    while current is not None:
        value = current.val

        if value in first_list_values and value not in added_values:
            tail.next = ListNode(value)
            tail = tail.next
            added_values.add(value)

        current = current.next

    return dummy_head.next


list1 = ListNode(1, ListNode(4, ListNode(2, ListNode(3))))
list2 = ListNode(4, ListNode(2, ListNode(4, ListNode(3))))

result = common_elements(list1, list2)
# Expected linked list: 4 -> 2 -> 3 -> None

Common Pitfalls

  • Duplicate values: Use added_values to prevent duplicate nodes in the output.

  • Empty lists: If either input list is empty, return None.

  • Single-element lists: These are handled by the same traversal logic.

  • Negative values: Hash sets support negative integers without special treatment.

  • Already sorted lists: Sorting is unnecessary; the result follows the second list’s order.

  • Cyclic lists: This implementation assumes both lists are acyclic. A cyclic list would cause an infinite traversal unless cycle detection is added separately.

  • Mutating the inputs: The function creates new nodes and does not change either input list.

38

How do you split a linked list into k consecutive parts?

Splitting a linked list into k consecutive parts means cutting one ordered sequence into k contiguous sublists without changing node order. A count-and-cut algorithm gives each part either floor(n / k) or ceil(n / k) nodes, where n is the list length.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Algorithm and Guarantees

  1. Detect whether the list contains a cycle; cyclic input is rejected because it has no unambiguous linear split.

  2. Traverse the list once to count its n nodes.

  3. Calculate:

  4. base = n // k, the minimum size of each part.

  5. extra = n % k, the number of parts that receive one additional node.

  6. Traverse again, cutting each part after its assigned number of nodes.

  7. Return the head of each resulting ListNode sublist. A part is represented by None when it is empty.

The first extra parts receive one additional node, producing the most balanced possible distribution. For example, six nodes split into four parts have lengths 2, 2, 1, 1.

A dummy sentinel head provides a stable starting reference and keeps the traversal logic uniform when the original head is empty. The original nodes are reused; they are not copied.

Code Example

from __future__ import annotations


class ListNode:
    def __init__(self, val: int, next: ListNode | None = None) -> None:
        self.val = val
        self.next = next


def split_linked_list(
    head: ListNode | None,
    k: int,
) -> list[ListNode | None]:
    """Split an acyclic linked list into k consecutive parts, allowing empty parts."""
    if k <= 0:
        raise ValueError("k must be a positive integer")

    sentinel = ListNode(0, head)

    # Reject cyclic input using Floyd's cycle detection.
    slow = sentinel.next
    fast = sentinel.next
    while fast is not None and fast.next is not None:
        assert slow is not None
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            raise ValueError("input list must be acyclic")

    # Count the nodes.
    length = 0
    current = sentinel.next
    while current is not None:
        length += 1
        current = current.next

    if length == 0:
        return [None] * k

    base, extra = divmod(length, k)
    current = sentinel.next
    parts: list[ListNode | None] = []

    # Cut and collect each consecutive part.
    for index in range(k):
        part_size = base + (1 if index < extra else 0)

        if part_size == 0:
            parts.append(None)
            continue

        assert current is not None
        part_head = current
        part_tail = current

        for _ in range(part_size - 1):
            assert part_tail is not None
            part_tail = part_tail.next

        assert part_tail is not None
        next_node = part_tail.next
        part_tail.next = None

        parts.append(part_head)
        current = next_node

    sentinel.next = None
    return parts


head = ListNode(
    1,
    ListNode(
        2,
        ListNode(3, ListNode(4, ListNode(5, ListNode(6)))),
    ),
)

parts = split_linked_list(head, 4)
print([
    [node.val for node in part] if part is not None else []
    for part in parts
])
# Expected output: [[1, 2], [3, 4], [5], [6]]

Walkthrough

For 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> None and k = 4:

Step Calculation Result
Count nodes n = 6 Six nodes found
Divide base = 1, extra = 2 Sizes are 2, 2, 1, 1
Cut part 1 Keep two nodes 1 -> 2 -> None
Cut part 2 Keep two nodes 3 -> 4 -> None
Cut part 3 Keep one node 5 -> None
Cut part 4 Keep one node 6 -> None

The final state is:

[1 -> 2 -> None] | [3 -> 4 -> None] | [5 -> None] | [6 -> None]

Complexity

Let n be the number of nodes and k the requested number of parts.

Case Time Reason
Best O(n + k) Linear traversals plus construction of k results
Average O(n + k) The work does not depend on node values or distribution
Worst O(n + k) Cycle detection, counting, and splitting are all linear
  • Auxiliary space: O(1) excluding the returned result, including Floyd’s detection pointers.

  • Result space: O(k) for the part heads.

  • The input’s O(n) storage is not counted, and the recursion stack is O(1) because the implementation is iterative.

  • If k <= n is guaranteed, time simplifies to O(n).

Linked Lists vs Arrays

Operation Linked list Array
Access by index O(n) O(1)
Insert after a known node O(1) O(n) due to shifting
Delete when the predecessor is known O(1) O(n) due to shifting
Storage for n values O(n) O(n)

Linked lists are advantageous when nodes are frequently connected or disconnected without shifting elements. Arrays are preferable when constant-time indexed access is important.

Common Pitfalls

  • Off-by-one errors: The part size counts nodes, so advancing to the tail requires part_size - 1 moves.

  • Forgetting to cut the tail: Without setting part_tail.next = None, one part may still lead into the next.

  • Losing the next node: Save part_tail.next before detaching the tail.

  • Empty input: The function returns k empty parts.

  • One node: It belongs to the first part; remaining parts are empty when k > 1.

  • Invalid k: k must be positive. If every part must be non-empty, also require k <= n.

  • Values and ordering: Duplicate, negative, sorted, or unsorted values do not affect the algorithm.

  • Cycles: The function raises ValueError rather than looping indefinitely.

  • Common follow-up: Interviewers may ask why two passes are needed, how to return arrays of values instead of node heads, or how to enforce non-empty parts.

39

How do you sum two numbers represented as linked lists?

The standard linked-list addition algorithm adds corresponding digits from least significant to most significant, carrying any overflow into the next position. A dummy head simplifies insertion and handles empty inputs uniformly.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Representation and Approach

This implementation assumes each list stores digits in reverse order—the usual representation for this problem.

  • 2 -> 4 -> 3 represents 342.

  • 5 -> 6 -> 4 represents 465.

  • The result 7 -> 0 -> 8 represents 807.

At each position:

  1. Read the current digit from each list, using 0 when a list is exhausted.

  2. Compute total = left_digit + right_digit + carry.

  3. Append total % 10 to the result.

  4. Set carry = total // 10.

  5. Continue until both lists and the carry are exhausted.

If digits are stored most-significant-first instead, reverse each list before using this method. Reversing the input lists in place uses O(1) auxiliary space but mutates the inputs; reversing copies preserves the inputs but requires O(n + m) additional space. Reverse the result afterward if a most-significant-first result is required.

Complexity and Linked Lists vs Arrays

For the reverse-order implementation:

  • Best case: O(max(n, m)) time for nonempty inputs; O(1) when both lists are empty.

  • Average case: O(max(n, m)) time.

  • Worst case: O(max(n, m)) time, including a final carry.

  • Auxiliary space: O(1), excluding the returned list. The input is not counted, and there is no recursion stack.

  • Output space: O(max(n, m)) for nonempty inputs and O(1) for two empty inputs.

Operation Linked list Array
Access by index O(n) O(1)
Insert after a known node O(1) O(n)
Delete after a known node O(1) O(n)
Append without a tail pointer O(n) O(1) amortized

Walkthrough

Inputs:

left:  2 -> 4 -> 3 -> None
right: 5 -> 6 -> 4 -> None
  1. 2 + 5 = 7; append 7, carry 0: result: 7 -> None

  2. 4 + 6 = 10; append 0, carry 1: result: 7 -> 0 -> None

  3. 3 + 4 + 1 = 8; append 8, carry 0: result: 7 -> 0 -> 8 -> None

Final result:

7 -> 0 -> 8 -> None

Code Example

from __future__ import annotations

from dataclasses import dataclass


@dataclass(slots=True)
class ListNode:
    val: int
    next: ListNode | None = None


def sum_two_numbers(
    left: ListNode | None,
    right: ListNode | None,
) -> ListNode:
    """Add two reverse-order digit lists and return the sum list."""
    dummy_head = ListNode(0)
    tail = dummy_head
    carry = 0

    while True:
        left_digit = left.val if left is not None else 0
        right_digit = right.val if right is not None else 0

        total = left_digit + right_digit + carry
        carry = total // 10

        tail.next = ListNode(total % 10)
        tail = tail.next

        if left is not None:
            left = left.next
        if right is not None:
            right = right.next

        if left is None and right is None and carry == 0:
            break

    result = dummy_head.next
    assert result is not None
    return result


left = ListNode(2, ListNode(4, ListNode(3)))
right = ListNode(5, ListNode(6, ListNode(4)))

result = sum_two_numbers(left, right)
print(result.val, result.next.val, result.next.next.val)
# Expected output: 7 0 8

Edge Cases and Best Practices

  • Empty input: A missing list is treated as zero; two empty lists produce a result list containing 0.

  • One element: Works without special handling.

  • Duplicates: Duplicated digit values are ordinary input and require no special treatment.

  • Negative numbers: Standard decimal digit lists do not support a sign; signed numbers need separate sign handling.

  • Leading zeros: The algorithm preserves them at the least-significant end. Trim them only if the required output forbids them.

  • Cycles: A cyclic list violates the numeric representation and would cause nontermination; validity should be guaranteed.

  • Already sorted input: Sorting is irrelevant because positions are added directly.

Common Pitfalls

  • Using the wrong digit order without checking the problem’s representation.

  • Forgetting to continue while a final carry exists.

  • Losing the carry by dividing before calculating the output digit.

  • Using % and // incorrectly for negative totals.

  • Returning the dummy node instead of dummy_head.next.

  • Forgetting to advance only non-None list pointers.

  • Mutating input lists when the problem permits modification; reversing a forward-order list in place does so.

40

How do you find the merge point of two linked lists?

The merge point of two acyclic singly linked lists is the first node object they share, not the first position containing equal values. Use two pointers that switch lists when one reaches None; they meet at the merge point, or both reach None if there is no intersection.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

  • Compare nodes by identity (is), not only by val.

  • Start one pointer at each list’s head.

  • Advance both pointers one node at a time.

  • When one pointer reaches None, redirect it to the other list’s head.

  • If the lists intersect, the pointers eventually reference the same node; otherwise, both reach None together.

  • The standard merge-point problem assumes acyclic lists. If a cycle is detected, this implementation raises ValueError because cyclic inputs do not necessarily define a unique merge point.

  • Local dummy head nodes provide uniform sentinel references without modifying or reconnecting the caller’s lists. Floyd’s fast-and-slow cycle detection uses constant auxiliary space.

Example Walkthrough

Before:

  • List A: 1 -> 2 -> 3 -> None

  • List B: 4 -> 5 -> 3 -> None

The pointer states are:

Step Pointer in A Pointer in B
Start 1 4
Advance 2 5
Advance 3 3

The pointers meet at the shared node containing 3.

After:

  • List A: 1 -> 2 -> 3 -> None

  • List B: 4 -> 5 -> 3 -> None

The operation does not mutate either list.

Complexity

Let n and m be the numbers of nodes in the two lists.

  • Best case: O(1) when the heads are already the same node or either list is empty.

  • Average case: O(n + m) because each list is traversed only a constant number of times.

  • Worst case: O(n + m) when there is no intersection and cycle detection must scan the lists.

  • Auxiliary space: O(1), excluding the input lists; no recursion is used, so there is no recursion-stack cost.

Code Example

from __future__ import annotations


class ListNode:
    def __init__(self, val: int, next: ListNode | None = None) -> None:
        self.val = val
        self.next = next


def find_merge_point(
    head1: ListNode | None,
    head2: ListNode | None,
) -> ListNode | None:
    """Return the first shared node, or None; reject cyclic inputs."""
    dummy1 = ListNode(0, head1)
    dummy2 = ListNode(0, head2)
    first = dummy1.next
    second = dummy2.next

    if first is second:
        return first

    if first is None or second is None:
        return None

    def has_cycle(head: ListNode | None) -> bool:
        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

    if has_cycle(first) or has_cycle(second):
        raise ValueError(
            "Cyclic lists are outside the standard acyclic merge-point problem."
        )

    pointer1 = first
    pointer2 = second

    while pointer1 is not pointer2:
        pointer1 = pointer1.next if pointer1 is not None else second
        pointer2 = pointer2.next if pointer2 is not None else first

    return pointer1


shared = ListNode(3)
head1 = ListNode(1, ListNode(2, shared))
head2 = ListNode(4, ListNode(5, shared))

result = find_merge_point(head1, head2)
print(result.val if result is not None else None)  # 3

Linked Lists vs Arrays

Operation Array Singly linked list
Access by index O(1) O(n)
Insert after a known position O(n) O(1)
Delete after a known position O(n) O(1)
Find a shared node by identity O(n + m) O(n + m)

Common Pitfalls

  • Comparing values instead of identity: Duplicate values do not establish an intersection.

  • Ignoring cycles: A traversal that stops only at None can loop forever on a cyclic list; detect cycles before using the standard algorithm.

  • Mutating the input: Do not reverse, reconnect, or change the links of either input list.

  • Incorrect complexity claims: Cycle detection must be included when analyzing the implementation’s best case.

  • Edge cases: Empty lists return None; one-element lists work correctly; negative values and already sorted inputs behave identically because values do not affect detection.

  • Common follow-up: Interviewers may ask for cycle-entry detection, intersection-node recovery, or how to determine whether two lists share an entire suffix.

41

Is a singly linked list a palindrome?

A singly linked list can be a palindrome when its node values read identically from the head to the tail and from the tail to the head. The links themselves are not compared; only the values stored in the nodes matter.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Palindrome Condition

A singly linked list is palindromic if each value has a corresponding equal value in the opposite half of the list.

  • An empty list is a palindrome.

  • A one-node list is a palindrome.

  • Duplicate and negative values are compared normally.

  • The standard definition assumes a finite, acyclic list; a cyclic list has no well-defined tail for this comparison.

Efficient Approach

An in-place solution uses O(n) time and O(1) auxiliary space:

  1. Use a dummy head as a sentinel so boundary handling does not require special cases for the first node.

  2. Traverse with slow and fast pointers to locate the midpoint.

  3. Detach and reverse the second half using previous, current, and next pointers.

  4. Compare the first half with the reversed second half.

  5. For an odd-length list, skip the middle node during comparison.

  6. Reverse the second half again to restore the original list, even if a mismatch was found.

A simpler alternative copies the values into an array and compares them with the reverse, but that requires O(n) additional space.

Walkthrough

Consider the list 1 -> 2 -> 3 -> 2 -> 1 -> None.

Stage List state or action
Original 1 -> 2 -> 3 -> 2 -> 1 -> None
Split First half 1 -> 2, middle 3, second half 2 -> 1
Reversed second half 1 -> 2
Comparison 1 equals 1; 2 equals 2; the middle node is ignored
Restored 1 -> 2 -> 3 -> 2 -> 1 -> None

Complexity

  • Best case: O(n) time, because finding the midpoint still requires traversal.

  • Average case: O(n) time.

  • Worst case: O(n) time, because each node is processed only a constant number of times.

  • Auxiliary space: O(1) for the iterative in-place approach, including pointer variables and the dummy node. The recursion stack is O(1) because no recursion is used. The input list is not counted, although it is temporarily modified and then restored.

  • Array-based alternative: O(n) time and O(n) additional space.

Approach Time Extra space When to use
Copy values into an array and compare with its reverse O(n) O(n) Simplicity is more important than memory usage
Reverse the second half in place O(n) O(1) Preferred when constant auxiliary space matters

Comparison with Arrays

Operation Singly linked list Array
Access by index O(n) O(1)
Insert or delete after a known predecessor O(1) O(n) due to shifting
Traversal O(n) O(n)

Linked lists are useful when frequent insertions and deletions are required, while arrays provide faster access by index.

Common Pitfalls

  • Comparing node identities instead of val values.

  • Failing to skip the middle node in an odd-length list.

  • Restoring the list only when the values match.

  • Assuming the list must already be sorted.

  • Forgetting that an empty list and a one-node list are palindromes.

  • Attempting this algorithm on a cyclic list without first addressing the cycle.

  • Interviewers may follow up by asking about reversing the entire list, finding the midpoint, detecting a cycle with Floyd’s algorithm, or removing the nth node from the end.

42

How do you find the cycle length in a linked list?

The cycle length is the number of distinct nodes in the loop. Because a cyclic linked list has no natural endpoint, this is the standard meaning of its “length”; Floyd’s fast-and-slow-pointer algorithm detects the cycle, and a second traversal counts its nodes.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

  1. Create a dummy sentinel head pointing to the original head. This simplifies empty-list and boundary handling without modifying the input.

  2. Initialize slow and fast at the sentinel.

  3. Move slow one node at a time and fast two nodes at a time.

  4. If fast reaches the end, there is no cycle.

  5. If the pointers meet, that node is somewhere inside the cycle. Traverse the cycle once, counting nodes until returning to the meeting node.

The meeting point is not necessarily the cycle’s entry node, but it is guaranteed to be inside the cycle, so it is sufficient for measuring the cycle length.

Step-by-Step Example

For the cyclic list:

1 -> 2 -> 3 -> 1 -> 2 -> 3 -> ...

Iteration slow fast
Start Dummy Dummy
1 1 2
2 2 1
3 3 3

After the pointers meet at node 3, traverse from that node:

3 -> 1 -> 2 -> 3

There are three distinct nodes, so the result is 3.

Before: 1 -> 2 -> 3 -> 1 -> 2 -> 3 -> ...
After: 1 -> 2 -> 3 -> 1 -> 2 -> 3 -> ... unchanged; the detected cycle length is 3.

Complexity and Edge Cases

Let n be the number of distinct reachable nodes.

  • Best time: O(1) for a one-node self-cycle, because detection and counting finish in a constant number of steps.

  • Average time: O(n) because detection traverses the list and counting traverses the cycle.

  • Worst time: O(n) when the cycle begins near the end of a long prefix.

  • Auxiliary space: O(1), excluding the input. The dummy sentinel and pointer variables use constant space, and there is no recursion stack.

  • No cycle: The function returns 0 after an O(n) traversal.

  • Empty input: The function returns 0.

  • One element: An acyclic one-element list returns 0; a self-cycle returns 1.

  • Duplicates and negative values: These do not affect the result because nodes are compared by identity, not by val.

  • Already sorted input: Node-value order is irrelevant, including when the input is already sorted.

  • Multiple components: If multiple independent linked lists are supplied, check each list separately because each has its own head.

Operation Linked list Array
Access by index O(n) O(1)
Insert after a known node O(1) O(n)
Delete a known node with its predecessor O(1) O(n)
Extra space per element One node reference No per-element reference

Code Example

from __future__ import annotations


class ListNode:
    def __init__(self, val: int, next: ListNode | None = None) -> None:
        self.val = val
        self.next = next


def cycle_length(head: ListNode | None) -> int:
    """Return the number of nodes in the cycle, or 0 if there is no cycle."""
    # Dummy sentinel avoids separate handling for empty and one-node cases.
    dummy_head = ListNode(0, head)
    slow = fast = dummy_head

    # Detect a cycle with Floyd's fast-and-slow-pointer algorithm.
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next

        if slow is fast:
            # The meeting node belongs to the cycle. Count its distinct nodes.
            assert slow is not None and slow.next is not None
            current = slow.next
            length = 1

            while current is not slow:
                current = current.next
                assert current is not None
                length += 1

            return length

    return 0


if __name__ == "__main__":
    first = ListNode(1)
    second = ListNode(2)
    third = ListNode(3)

    first.next = second
    second.next = third
    third.next = first

    print(cycle_length(first))  # 3

Common Pitfalls

  • Off-by-one errors: Initialize the count to 1 for the meeting node, then count each additional distinct node.

  • Comparing values instead of identities: A cycle may contain duplicate values; compare ListNode objects with is.

  • Assuming the meeting point is the entry node: Floyd’s detection phase can meet anywhere in the cycle.

  • Mutating the input: The dummy sentinel only points to the original head; the original links remain unchanged.

  • Using recursion: An iterative solution avoids recursion-depth limits.

  • Forgetting the no-cycle case: Check fast and fast.next before advancing.

Common follow-up questions include finding the cycle’s entry node, removing the cycle, and calculating the total number of distinct nodes including the prefix before the cycle.

43

Duplicate a linked list with random pointers in O(1) space

Use node interleaving to place each copied node immediately after its original, copy the random pointers while the lists are interleaved, and then separate the two lists. This requires O(1) auxiliary space, although the returned copy necessarily requires O(n) output space.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

The standard next-linked list is copied in three passes:

  1. Interleave the nodes

  2. Insert a clone immediately after each original node.

  3. The original order becomes original -> clone -> original -> clone.

  4. Copy random pointers

  5. For every original node, its corresponding clone is original.next.

  6. Therefore, the cloned random pointer is original.random.next, when original.random is not None.

  7. Split the lists

  8. Connect each clone only to the next clone.

  9. Restore the original list to its original next pointers.

A dummy sentinel node is used for the copied list. It removes special handling for the copied head and gives the function one consistent return path.

State Walkthrough

For a list containing 7 -> 13 -> 11 -> None:

Stage next structure
Original 7 -> 13 -> 11 -> None
After interleaving 7 -> 7' -> 13 -> 13' -> 11 -> 11' -> None
After splitting 7' -> 13' -> 11' -> None

Suppose the original random pointers are 7.random = 11, 13.random = 7, and 11.random = None. The copied random pointers become 7'.random = 11', 13'.random = 7', and 11'.random = None.

Complexity

Measure Best Average Worst Reason
Time O(n) O(n) O(n) Every node and random pointer is processed a constant number of times
Auxiliary space O(1) O(1) O(1) Only pointers and a constant number of variables are used
Output space O(n) O(n) O(n) The cloned list contains n new nodes
Recursion stack O(1) O(1) O(1) The implementation is iterative

The input is not counted as auxiliary space. If the returned copy is included in the total space calculation, the result is O(n), not O(1).

Linked Lists Compared with Arrays

Operation Linked list Array
Access by position O(n) O(1)
Insert near a known node O(1) if its predecessor is known O(n) because elements may shift
Delete near a known node O(1) if its predecessor is known O(n) because elements may shift
Copy with random pointers O(n) time and O(1) auxiliary space using interleaving O(n) time and O(n) space for the copy

Code Example

from __future__ import annotations


class ListNode:
    def __init__(
        self,
        val: int,
        next: ListNode | None = None,
        random: ListNode | None = None,
    ) -> None:
        self.val = val
        self.next = next
        self.random = random


def duplicate_with_random(head: ListNode | None) -> ListNode | None:
    """Return a deep copy of a linked list, including its random pointers."""
    if head is None:
        return None

    # Pass 1: insert each clone immediately after its original node.
    current = head
    while current is not None:
        original_next = current.next
        clone = ListNode(current.val)

        current.next = clone
        clone.next = original_next
        current = original_next

    # Pass 2: copy random pointers using the interleaved structure.
    current = head
    while current is not None:
        clone = current.next
        assert clone is not None

        if current.random is not None:
            clone.random = current.random.next

        current = clone.next

    # Pass 3: split the clones from the originals and restore the original list.
    copy_dummy = ListNode(0)
    copy_tail = copy_dummy
    current = head

    while current is not None:
        clone = current.next
        assert clone is not None

        original_next = clone.next
        # Restore original list's next pointer
        current.next = original_next
        # Set clone's next to the next clone (or None)
        clone.next = original_next.next if original_next is not None else None

        copy_tail.next = clone
        copy_tail = clone
        current = original_next

    return copy_dummy.next


original = ListNode(7)
original.next = ListNode(13)
original.next.next = ListNode(11)
original.random = original.next.next
original.next.random = original

copied = duplicate_with_random(original)

assert copied is not None
assert copied.next is not None
assert copied.next.next is not None

print(
    copied.val,
    copied.next.val,
    copied.next.next.val,
    copied.random.val,
    copied.next.random.val,
)
# Output: 7 13 11 11 7

Common Pitfalls

  • Misstating the space requirement: O(1) means auxiliary space excluding the returned copy. Counting the output gives O(n).

  • Copying random pointers too early: current.random.next identifies the cloned random target only after interleaving is complete.

  • Splitting before copying random pointers: This removes the mapping needed to locate cloned random targets.

  • Mutating the original: The original list is temporarily modified but is restored by the final pass.

  • Ignoring cycles: Random-pointer cycles are copied correctly, but the next chain itself is assumed to be finite and acyclic.

  • Unnecessary special cases: Empty, single-node, duplicate-valued, and negative-valued lists are handled naturally.

  • Typical follow-up: Interviewers may ask for the hash-map alternative, which takes O(n) extra space but is simpler and can handle more general pointer structures.

44

How can I detect whether two singly linked lists share a node in O(1) space?

Intersection means the two singly linked lists share the same node object, not merely that their val fields are equal. The solution uses two pointers that switch lists when they reach None, while a small Floyd-style cycle check handles cyclic lists without a visited set.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

For ordinary acyclic lists, maintain one pointer for each list:

  1. Move both pointers one node at a time.

  2. When a pointer reaches None, redirect it to the other list’s head.

  3. If the pointers become the same object, the lists intersect.

  4. If both pointers reach None together, the lists do not intersect.

Switching lists compensates for different lengths. For example:

List A: 1 -> 2 -> None
List B: 3 -> 2 -> None

Here, the node containing 2 must be the same node object. The pointers eventually meet at that node.

The code also detects cycles with Floyd’s algorithm. If both lists are cyclic, they intersect exactly when their cycles overlap. The code checks whether one cycle entry occurs on the other cycle; equal entries are handled directly. This remains constant-space and prevents infinite loops for disjoint cyclic lists.

Complexity

Let m and n be the numbers of reachable nodes in the two lists.

  • Best case: O(1) when both heads are already the same node or both lists are empty.

  • Average case: O(m + n) for ordinary inputs; formally, an average requires a specified probability distribution.

  • Worst case: O(m + n) because the pointers may traverse both lists and their cycles.

  • Auxiliary space: O(1). The input lists are not counted, there is no recursion stack, and the sentinel nodes and pointers are constant in number.

Comparison with Arrays

Operation Singly linked list Array
Access by index O(n) O(1)
Insert after a known node O(1) O(n) due to shifting
Delete a known node O(1) O(n) due to shifting
Find a shared node with the method above O(m + n) time, O(1) space Usually requires hashing or index tracking

The lists are not modified:

Before: A1 -> A2 -> None
        B1 -> A2 -> None

After:  A1 -> A2 -> None
        B1 -> A2 -> None

Code Example

from __future__ import annotations


class ListNode:
    def __init__(self, val: int, next: ListNode | None = None) -> None:
        self.val = val
        self.next = next


def _cycle_info(
    head: ListNode | None,
) -> tuple[ListNode | None, int]:
    """Return the cycle entry and cycle length, or (None, 0) if acyclic."""
    if head is None:
        return None, 0

    slow = head
    fast = head

    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next

        if slow is fast:
            # Find the first node of the cycle.
            entry = head
            while entry is not slow:
                entry = entry.next
                slow = slow.next

            # Measure the cycle length.
            length = 1
            current = entry.next
            while current is not entry:
                length += 1
                current = current.next

            return entry, length

    return None, 0


def lists_intersect(
    head1: ListNode | None,
    head2: ListNode | None,
) -> bool:
    """Return True if the lists share the same node object."""
    # A shared head immediately proves intersection.
    if head1 is not None and head1 is head2:
        return True

    # Sentinel heads simplify switching pointers without changing the lists.
    dummy1 = ListNode(0, head1)
    dummy2 = ListNode(0, head2)

    cycle_entry1, _ = _cycle_info(dummy1.next)
    cycle_entry2, cycle_length2 = _cycle_info(dummy2.next)

    # An acyclic list cannot intersect a cyclic list.
    if (cycle_entry1 is None) != (cycle_entry2 is None):
        return False

    # Both lists are cyclic. Check whether their cycles overlap.
    if cycle_entry1 is not None and cycle_entry2 is not None:
        if cycle_entry1 is cycle_entry2:
            return True

        current = cycle_entry2
        for _ in range(cycle_length2):
            if current is cycle_entry1:
                return True
            current = current.next

        return False

    # Both lists are acyclic: use the constant-space pointer-switching method.
    pointer1 = dummy1.next
    pointer2 = dummy2.next

    while pointer1 is not pointer2:
        pointer1 = pointer1.next if pointer1 is not None else dummy2.next
        pointer2 = pointer2.next if pointer2 is not None else dummy1.next

    return pointer1 is not None


# Both lists point to the same node object.
shared = ListNode(2)
head1 = ListNode(1, shared)
head2 = ListNode(3, shared)

print(lists_intersect(head1, head2))  # True

Common Pitfalls

  • Comparing values instead of identity: Two nodes can both contain 2 without being the same node. Use is, not ==.

  • Confusing a common value with intersection: This problem usually means a shared node object, which is stronger than matching values.

  • Forgetting the sentinel transition: When one pointer reaches None, it must continue from the other list’s head.

  • Infinite loops with cyclic lists: The cycle-aware portion prevents a cyclic list from causing an endless traversal.

  • Edge cases: Empty lists are handled, single-element lists work, and duplicate or negative values do not affect the result because node identity is used. Sortedness is irrelevant, and graph disconnection is not applicable to this linked-list operation.

45

How do you rotate a linked list right by k positions?

A right rotation moves the last k nodes to the front while preserving the order of all nodes. The standard approach finds the list length, locates the new tail, and reconnects the list in one pass.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

Assume the list is finite, singly linked, and contains n nodes. A rotation by k is equivalent to a rotation by k % n, so large values of k are handled efficiently.

  1. Find the length and the last node.

  2. If k == 0, return the original head.

  3. Locate the node that will become the new tail. It is the node n - k positions from the head.

  4. Break the list after that node.

  5. Connect the original tail to the original head.

  6. Return the node after the new tail.

A dummy sentinel head simplifies changing the list’s head. It is used only during the operation and is not part of the returned list.

For the list:

1 -> 2 -> 3 -> 4 -> 5 -> None

Rotating right by 2 gives:

4 -> 5 -> 1 -> 2 -> 3 -> None

This implementation uses right rotation. A left rotation by k is equivalent to a right rotation by n - k.

Complexity

For a list of n nodes:

  • Best case: O(n) time. The list must be traversed to determine its length and validate that it is acyclic.

  • Average case: O(n) time. The same traversals are required.

  • Worst case: O(n) time. The algorithm performs a constant number of linear traversals.

  • Auxiliary space: O(1). Only pointers, counters, and the dummy node are used; there is no recursion stack. The input list itself occupies O(n) space but is not counted as auxiliary space.

Code Example

from __future__ import annotations


class ListNode:
    def __init__(self, val: int, next: ListNode | None = None) -> None:
        self.val = val
        self.next = next


def rotate_list(head: ListNode | None, k: int) -> ListNode | None:
    """Rotate a finite singly linked list right by k positions."""
    if head is None:
        return None

    # Detect cycles with Floyd's fast and slow pointers.
    slow = head
    fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            raise ValueError("Cannot rotate a list containing a cycle")

    # Dummy sentinel makes head updates uniform.
    dummy = ListNode(0, head)
    tail = dummy
    length = 0

    while tail.next is not None:
        tail = tail.next
        length += 1

    k %= length
    if k == 0:
        return head

    # Find the node immediately before the new head.
    new_tail = dummy
    for _ in range(length - k):
        new_tail = new_tail.next

    new_head = new_tail.next
    new_tail.next = None
    tail.next = head
    dummy.next = new_head

    return dummy.next


def list_values(head: ListNode | None) -> list[int]:
    values: list[int] = []
    current = head

    while current is not None:
        values.append(current.val)
        current = current.next

    return values


head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
result = rotate_list(head, 2)

print(list_values(result))
# Expected output: [4, 5, 1, 2, 3]

Edge Cases and Linked Lists Versus Arrays

  • Empty list: Returns None.

  • One-element list: Returns the same node; every rotation is equivalent.

  • k greater than the length: Uses k % length.

  • Negative k: Python’s modulo normalizes it; for example, -1 behaves like a right rotation by length - 1.

  • Duplicate or negative node values: Rotation is based on node positions, not values, so both work normally.

  • Already sorted input: Sorting is irrelevant to linked-list rotation.

  • Cycles: The code detects them with Floyd’s algorithm and raises ValueError, since rotating a cyclic list has no standard definition.

  • Disconnected components: A linked list represents one connected chain; separate components should be handled as separate lists.

Operation Singly linked list Array
Access by index O(n) O(1)
Insertion at a known node O(1) O(n) due to shifting
Deletion at a known node O(1) O(n) due to shifting
Rotation O(n) O(n)

Common Pitfalls

  • Off-by-one errors: The new tail is the node before the new head, so move n - k steps from the dummy node.

  • Confusing left and right rotation: Confirm the expected direction; this code rotates right.

  • Mutating the input: Rotation intentionally changes the links of the original nodes, so callers should not expect the original list structure to remain unchanged.

  • Forgetting cycle detection: An unbounded traversal can loop forever on a cyclic list. This implementation uses Floyd’s fast and slow pointers rather than a visited set.

  • Using list.insert(0, x) or list.pop(0) in a loop: These array operations are O(n) and can make an otherwise linear algorithm quadratic.

  • Common follow-up questions: Interviewers may ask about left rotation, rotating by k % n, detecting cycles, reversing the list, or explaining why the dummy node simplifies the implementation.

46

What is the time complexity of common linked list operations?

The time complexity of a linked-list operation depends mainly on whether the required node is already available. Access through an existing node reference is O(1), while traversing or searching for a node takes O(n); insertion after a known node is O(1), but deleting a non-head node from a singly linked list requires finding its predecessor and therefore takes O(n).

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Complexity by Operation

The following distinctions assume a singly linked list with val and next fields unless another type is stated.

Operation Best Average Worst Reason
Access by index O(1) O(n) O(n) Index 0 uses the head directly; other indices require traversal.
Search by value O(1) O(n) O(n) A match at the head is immediate; otherwise nodes must be checked.
Traversal O(n) O(n) O(n) Every node is visited once.
Insert at head O(1) O(1) O(1) Only the new node and head pointer change.
Insert at tail with a maintained tail pointer O(1) O(1) O(1) The previous tail can be linked directly to the new node.
Insert at tail without a tail pointer O(n) O(n) O(n) The list must be traversed to locate its tail.
Insert after a known node O(1) O(1) O(1) Only a constant number of pointers change.
Delete the head O(1) O(1) O(1) The head pointer advances by one node.
Delete a known non-head node, singly linked O(n) O(n) O(n) The predecessor must be found before relinking it.
Delete a known node, doubly linked O(1) O(1) O(1) The node’s prev pointer identifies its predecessor directly.
Delete by value O(1) O(n) O(n) The target is immediate at the head or requires a search.
Delete the tail, singly linked O(n) O(n) O(n) The tail has no predecessor pointer, so the list must be traversed.
Delete the tail, doubly linked O(1) O(1) O(1) The tail’s prev pointer identifies its predecessor.
Reverse a list O(n) O(n) O(n) Every node is visited and relinked.
Count nodes O(n) O(n) O(n) Every node must be visited.
Copy a list O(n) O(n) O(n) One new node is allocated per original node.
Detect a cycle O(n) O(n) O(n) Floyd’s fast and slow pointers eventually meet in a cyclic list.
Merge two sorted lists O(n + m) O(n + m) O(n + m) Each node from both inputs is processed at most once.

Why Node Location Matters

The critical distinction is between operating on a known node and finding that node first.

  • Known node: Access is O(1), and insertion after it is O(1).

  • Deletion in a singly linked list: A non-head node’s predecessor must first be found, making deletion O(n).

  • Doubly linked list: A prev pointer allows deletion of a known node in O(1).

  • Tail pointer: Maintaining a pointer to the last node makes tail insertion O(1).

For example, deleting value 3 has these states:

  • Before: 1 -> 2 -> 3 -> 4 -> None

  • Search: 1 -> 2 -> 3

  • After: 1 -> 2 -> 4 -> None

The unlinking is O(1), but locating 3 makes the complete singly linked-list operation O(n).

Linked Lists Compared with Arrays

Operation Linked List Array
Access by index O(n) O(1)
Search by unsorted value O(n) O(n)
Insert at head O(1) O(n)
Insert after a known linked-list node O(1) O(n)
Delete a known linked-list node O(n) singly; O(1) doubly O(n)
Insert or delete at a known array index O(n) O(n)
Per-element storage Usually a next pointer, plus prev when needed No per-element link pointer

Linked lists favor structural changes when a node reference is already known. Arrays favor random access and compact contiguous storage.

Space Complexity and Sentinel Nodes

  • Auxiliary space for iterative traversal, reversal, insertion, and deletion is O(1).

  • Recursive reversal or traversal uses O(n) additional space because the recursion stack contains one frame per node.

  • Copying a list requires O(n) additional space.

  • The input list occupies O(n) space but is normally excluded from auxiliary space analysis.

  • A dummy or sentinel head simplifies front insertion and deletion by treating the head like another node. It uses O(1) extra space without changing the asymptotic complexity.

Common Pitfalls and Interview Tips

  • Do not describe searching as O(1); only access through an existing node reference is O(1).

  • Tail insertion is O(1) only when a tail pointer is maintained.

  • In a singly linked list, deleting the tail is O(n), while deleting the head is O(1).

  • Reversal with recursion uses O(n) stack space; iterative prev/curr/next reversal uses O(1).

  • Always handle an empty list, a one-node list, duplicates, and deleting the head or tail.

  • Floyd’s cycle detection uses O(n) time and O(1) auxiliary space because the pointers advance at different rates.

  • Common follow-ups include finding the middle node, reversing the list, removing the nth node from the end, and merging two sorted lists.

47

What is the space complexity of linked lists with auxiliary pointers?

Auxiliary space for an operation on an ordinary linked list is O(1) when the operation uses a constant number of local pointers and the input list is excluded. The list’s persistent storage is O(n), including its node objects and link fields.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Space Model

A linked list containing n elements has two relevant storage categories:

  • Persistent storage: Each node stores a value and one or more links, so the complete list occupies O(n) space. This includes the input list itself.

  • Auxiliary storage: Extra working memory used by an operation. Variables such as current, previous, next_node, fast, and slow occupy O(1) auxiliary space regardless of the list length.

Extra pointers stored inside every node are part of the data structure, not auxiliary space for an operation. If every node has a fixed number k of additional links, persistent pointer storage is O(nk), which is O(n) when k is constant. Augmented structures may have different bounds: a variable-height skip list uses expected O(n) persistent pointer storage, while fixed L-slot tower arrays use O(nL).

A dummy sentinel head adds only one node, or O(1) persistent space, and simplifies operations at the beginning of the list. Recursive traversal is different from iterative traversal: its auxiliary space is O(n) because the recursion stack contains one frame per node. An iterative traversal uses O(1) auxiliary space and avoids Python’s recursion-depth limit.

Complexity

Auxiliary-space figures below exclude the input list but include the recursion stack.

Operation Best time Average time Worst time Auxiliary space Reason
Search by value O(1) O(n) O(n) O(1) A constant number of pointers is used; the target may occur anywhere.
Traverse O(n) O(n) O(n) O(1) Every node is visited, using only a current pointer.
Insert or delete after a known node O(1) O(1) O(1) O(1) Links are changed directly once the node is available.
Reverse iteratively O(n) O(n) O(n) O(1) Uses previous, current, and next_node pointers.
Detect a cycle with fast and slow pointers O(n) O(n) O(n) O(1) Floyd’s algorithm needs only two moving pointers.
Traverse recursively O(n) O(n) O(n) O(n) The call stack grows with the number of nodes.

For an augmented structure, an insertion or deletion that records predecessors at all configured levels needs O(L) auxiliary space for that vector. If the maximum height scales as the expected height, expected search and update time is O(log n); with L traversed levels, the general worst-case time is O(nL).

Pointer Patterns and Edge Cases

  • Reversal: Maintain previous, current, and next_node. Before: 1 -> 2 -> 3 -> None; after: 3 -> 2 -> 1 -> None. Auxiliary space remains O(1).

  • Cycle detection: Fast and slow pointers detect a cycle with O(1) auxiliary space. A normal traversal without cycle detection may loop forever.

  • Dummy sentinel: Use a sentinel to remove special cases for insertion or deletion at the front; it changes total space by only O(1).

  • Empty input: A traversal checks the initial null pointer immediately.

  • One element: Traversal and cycle detection both terminate after constant work.

  • Duplicates and negative values: Neither changes the asymptotic space requirements.

  • Already sorted input: Sorting does not provide random access, so searching still takes O(n).

  • Disconnected structures: A standalone linked list has no disconnected-graph case; multiple independent lists must be traversed separately.

Arrays vs Linked Lists

Operation Linked list Array
Access by index O(n) O(1)
Search by value O(n) O(n)
Insert or delete at the front O(1) O(n)
Insert or delete at a known location O(1) once the node is known O(n) due to shifting
Delete by value O(n) to locate, then O(1) O(n)
Traverse O(n) O(n)
Total storage O(n) O(n)

Common Pitfalls

  • Conflating input and auxiliary space: Persistent node and link storage is not the same as temporary pointer variables.

  • Ignoring the recursion stack: Recursive traversal requires O(n) auxiliary space.

  • Assuming deletion is always O(1): Only deletion after a known node is O(1); finding the node by value costs O(n).

  • Mutating the input: Reversal, insertion, and deletion change link order and should be documented explicitly.

  • Off-by-one errors: Define whether the sentinel belongs to the visible list and handle the empty and one-element cases.

  • Cycles and integer overflow: Traversals need cycle detection, and languages with fixed-width integers can overflow when values or indices are transformed.

48

How does recursion affect linked list time and space complexity?

Recursion adds a call stack to linked-list operations: time usually remains proportional to the nodes visited, but auxiliary space becomes proportional to the recursion depth. An iterative operation uses O(1) auxiliary space, whereas a recursive traversal or reversal of an n-node list can require O(n) stack space.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Recursion Changes Analysis

For a linked list with n nodes:

  • Recursive traversal or search:

  • Best time: O(1) when the target is the first node or the list is empty.

  • Average time: O(n) because a uniformly random position requires visiting about half the nodes.

  • Worst time: O(n) when the target is at the end or is absent.

  • Auxiliary space: O(h), where h is the recursion depth; this is O(n) in the worst case because each call remains on the stack.

  • Recursive reversal:

  • Time: O(n) because every node is visited once.

  • Auxiliary space: O(n) because one stack frame is active per node.

  • Iterative traversal or reversal:

  • Time: O(n).

  • Auxiliary space: O(1) because only a small number of variables are maintained.

Recursion does not automatically make an operation asymptotically slower. Its main effect is space usage and constant-factor overhead from function calls. However, an implementation that repeatedly traverses the list at each recursive level can become O(n²).

The input list itself is normally excluded from auxiliary space. If total memory is counted, an iterative operation still uses O(n) total space for the input, while a recursive reversal uses O(n) for the input plus up to O(n) for the call stack.

Linked Lists Compared with Arrays

Operation Linked list Array
Access by index O(n) average and worst; O(1) best O(1)
Find a value O(n) worst O(n) worst
Insert after a known node O(1) O(n) because elements shift
Delete a known node O(1) O(n) because elements shift
Recursive traversal stack O(n) worst O(n) worst
Iterative traversal stack O(1) O(1)

The linked-list insertion and deletion costs assume the target node is already known. Finding that node still takes O(n) time.

Recursive Reversal Example

The list before reversal is:

1 -> 2 -> 3 -> None

The recursive steps are:

  1. Recurse until the last node is reached.

  2. Reverse each next pointer while returning through the call stack.

  3. The resulting list is:

3 -> 2 -> 1 -> None

A dummy head is used to hold the result and avoid separate special cases for replacing the original head.

Code Example

class ListNode:
    def __init__(self, val: int, next: "ListNode | None" = None) -> None:
        self.val = val
        self.next = next


def has_cycle(head: ListNode | None) -> bool:
    """Return whether a singly linked list contains a cycle."""
    slow = head
    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 reverse_recursively(head: ListNode | None) -> ListNode | None:
    """Reverse an acyclic singly linked list using recursion."""
    dummy = ListNode(0, head)

    if has_cycle(dummy.next):
        raise ValueError("Cannot reverse a linked list containing a cycle.")

    def reverse(node: ListNode | None) -> ListNode | None:
        if node is None or node.next is None:
            return node

        new_head = reverse(node.next)
        node.next.next = node
        node.next = None
        return new_head

    dummy.next = reverse(dummy.next)
    return dummy.next


head = ListNode(1, ListNode(2, ListNode(3)))
reversed_head = reverse_recursively(head)
# Expected list: 3 -> 2 -> 1 -> None

The cycle check prevents infinite recursion. Duplicate values and negative values are handled normally because reversal depends on links, not values. Empty lists and one-element lists also work.

Common Pitfalls

  • Ignoring the recursion stack: A recursive O(n) operation may use O(n) auxiliary space, not O(1).

  • Exceeding Python’s recursion limit: Python’s default limit is approximately 1000 calls. Long lists should use an iterative reversal or an explicit stack.

  • Mutating the input: Reversal changes the original list’s links. Clone the list if the caller must retain the original.

  • Forgetting cycle detection: Recursive traversal of a cyclic list never reaches None.

  • Confusing known-node operations with search: Insertion or deletion after a known node is O(1), but locating that node is O(n).

  • Irrelevant edge cases: Already sorted input does not change the reversal complexity. Disconnected graphs do not apply to a single linked list; if adjacency lists are used, each component must be processed separately.

  • Common follow-up: Interviewers often ask for an iterative reversal using a prev, curr, and next pointer pattern, which reduces auxiliary space to O(1).

49

How do you find the intersection of two Y-shaped linked lists?

The intersection point is the first node object shared by two singly linked lists that merge into a common suffix. Find it by comparing node identity—not node values—after aligning the lists to the same length.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Approach

Assume the lists are acyclic and each list has its own prefix followed by a shared suffix.

  1. Traverse both lists to calculate their lengths.

  2. Advance the longer list until both pointers are equally far from their starting points.

  3. Move both pointers together.

  4. The first pair that references the same node is the intersection. If both pointers become None, there is no intersection.

The code uses a dummy sentinel head for each list. Its .next points to the first real node, and its .next is None for an empty list. This provides a stable boundary and avoids special handling when a list has no elements.

Approach Time Auxiliary space When to use
Check every node in one list against every node in the other O(m × n) O(1) Only for very short lists
Align lengths, then scan in lockstep O(m + n) O(1) Preferred general solution

Here, m and n are the lengths of the two input lists, counting shared nodes independently in each list.

Example Walkthrough

The lists converge at the node with value 4:

A: [dummy] -> 1 -> 2 -> 4 -> 5 -> None
B: [dummy] -> 3 -> 4 -> 5 -> None
Step Pointer in A Pointer in B Result
Initial 1 3 Lengths differ
Align lengths 2 3 Remaining lengths match
Lockstep step 1 2 3 Different node objects
Lockstep step 2 4 4 Same node object: intersection

After the operation, the input lists are unchanged, and the function returns the shared node with value 4:

A: [dummy] -> 1 -> 2 -> 4 -> 5 -> None
B: [dummy] -> 3 -> 4 -> 5 -> None
Result: shared node with value 4

Duplicate values do not indicate an intersection. For example, two different nodes can both contain 3; only node_a is node_b proves that they are shared.

Complexity

  • Best-case time: O(m + n), because the implementation scans both lists to determine their lengths.

  • Average-case time: O(m + n), since traversal time is deterministic.

  • Worst-case time: O(m + n), including the alignment and lockstep scan.

  • Auxiliary space: O(1), excluding the input lists. The implementation is iterative, so there is no recursion stack.

Linked Lists vs Arrays

Operation Singly linked list Array
Access by index O(n) O(1)
Insert after a known node O(1) O(n) due to shifting
Delete a known node with a known predecessor O(1) O(n) due to shifting
Find a node with a given value O(n) O(n)

Linked lists are advantageous when nodes are already referenced or frequently linked and unlinked. Arrays are better for indexed access and cache-friendly storage.

Code Example

from __future__ import annotations

from dataclasses import dataclass


@dataclass(slots=True)
class ListNode:
    val: int
    next: ListNode | None = None


def find_intersection(
    head_a: ListNode,
    head_b: ListNode,
) -> ListNode | None:
    """Find the first shared node of two sentinel-headed linked lists."""
    pointer_a = head_a.next
    pointer_b = head_b.next

    length_a = 0
    length_b = 0

    while pointer_a is not None:
        length_a += 1
        pointer_a = pointer_a.next

    while pointer_b is not None:
        length_b += 1
        pointer_b = pointer_b.next

    # Align the pointers by advancing the longer list.
    while length_a > length_b:
        pointer_a = pointer_a.next if pointer_a is not None else None
        length_a -= 1

    while length_b > length_a:
        pointer_b = pointer_b.next if pointer_b is not None else None
        length_b -= 1

    # Compare node identity, not values.
    while pointer_a is not pointer_b:
        pointer_a = pointer_a.next if pointer_a is not None else None
        pointer_b = pointer_b.next if pointer_b is not None else None

    return pointer_a


# Build two Y-shaped lists with sentinel heads.
head_a = ListNode(0)
head_b = ListNode(0)

shared_tail = ListNode(4)
shared_tail.next = ListNode(5)

current = head_a
for value in (1, 2):
    current.next = ListNode(value)
    current = current.next
current.next = shared_tail

current = head_b
current.next = ListNode(3)
current = current.next
current.next = shared_tail

result = find_intersection(head_a, head_b)
print(result.val if result is not None else None)  # 4

Common Pitfalls and Interview Tips

  • Comparing values: Equal values do not mean equal nodes; always compare object identity.

  • Ignoring the shared suffix: The lists may have different lengths before reaching the common node.

  • Mutating the input: The algorithm should only move temporary pointers.

  • Empty or one-element lists: Sentinel-headed empty lists are represented by .next is None; one-element lists are handled naturally.

  • Duplicate and negative values: Values have no effect on the identity-based algorithm.

  • Cycles: Cyclic lists are outside the Y-shaped assumption and require a separate cycle-handling strategy.

  • Sorted input: Sorting is unnecessary and would add O(m log m) or O(n log n) work.

  • Disconnected graphs: Not applicable to this linked-list problem.

  • Integer overflow: Not an issue in Python; use an adequately sized type in languages with fixed-width integers.

A common follow-up asks how to detect a cycle using fast and slow pointers with Floyd’s algorithm.

50

How do you segregate nodes by parity in a singly linked list?

The standard algorithm performs a stable partition of a singly linked list by moving nodes with even val values before nodes with odd val values. It reuses the original nodes and preserves the relative order within the even and odd groups.

Read full answer

Applies toPython 3.12

How It Works

Two dummy sentinel head nodes are created: one for even nodes and one for odd nodes. Sentinel heads simplify handling of the first node in each group because the algorithm can use identical append logic for every node.

  • Even tail: Tracks the last even node.

  • Odd tail: Tracks the last odd node.

  • Current: Points to the node currently being processed.

  • Next node: Stores the remainder of the list before the current node is detached and appended to a group.

The two chains are then connected, placing the odd chain after the even chain.

For this list:

1 -> 2 -> 3 -> 4 -> None

The result is:

2 -> 4 -> 1 -> 3 -> None

The algorithm proceeds as follows:

  1. 1 is odd, so it is appended to the odd chain.

  2. 2 is even, so it is appended to the even chain.

  3. 3 is odd, so it is appended after 1.

  4. 4 is even, so it is appended after 2.

  5. The even chain is connected to the odd chain.

Complexity

  • Best case: O(n) — every node must be visited and classified.

  • Average case: O(n) — every node must be visited and classified.

  • Worst case: O(n) — every node must be visited and classified.

  • Auxiliary space: O(1) — only two dummy nodes and a constant number of pointers are used. There is no recursion stack.

  • Total space including the input list: O(n). The original nodes are reused rather than copied.

Linked List vs Array

Operation Singly linked list Array
Access by index O(n) O(1)
Insert at a known node O(1) O(n)
Delete at a known node O(1) O(n)
Traverse all elements O(n) O(n)

Linked lists favor pointer-based reorganization, while arrays are better for constant-time indexed access.

Code Example

from __future__ import annotations

from dataclasses import dataclass


@dataclass
class ListNode:
    val: int
    next: ListNode | None = None


def segregate_even_odd(head: ListNode | None) -> ListNode | None:
    """Move even-valued nodes before odd-valued nodes, preserving group order."""
    even_dummy = ListNode(0)
    odd_dummy = ListNode(0)
    tail_even = even_dummy
    tail_odd = odd_dummy

    current = head

    while current is not None:
        # Save the remaining list before detaching the current node.
        next_node = current.next
        current.next = None

        if current.val % 2 == 0:
            tail_even.next = current
            tail_even = current
        else:
            tail_odd.next = current
            tail_odd = current

        current = next_node

    # Connect the odd chain after the complete even chain.
    tail_even.next = odd_dummy.next
    return even_dummy.next


node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node4 = ListNode(4)
node1.next = node2
node2.next = node3
node3.next = node4

result = segregate_even_odd(node1)
# Expected: 2 -> 4 -> 1 -> 3 -> None

Common Pitfalls

  • Confusing values with positions: “Even” and “odd” refer to node.val, not the node’s position in the list.

  • Losing the remaining list: Save current.next before changing any pointers.

  • Returning a dummy node: Return even_dummy.next, not even_dummy.

  • Unexpected input mutation: This algorithm intentionally rearranges the original nodes. Copy the values into new nodes if the input must remain unchanged.

  • Edge cases: An empty list returns None; a one-node list remains valid; duplicates remain in their group; negative even and odd values are classified correctly; and an already segregated list remains unchanged.

51

How do you sort an alternating-order linked list in ascending order?

For a list whose 1-based odd-positioned values are nondecreasing and even-positioned values are nonincreasing, split, reverse, and merge produces an ascending list. Reversing the even-positioned chain makes both chains ascending, allowing a standard linear-time merge.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Idea

  • Extract nodes at odd positions into one chain.

  • Extract nodes at even positions into another chain.

  • The odd-position chain is already ascending.

  • The even-position chain is descending, so reverse it.

  • Merge the two ascending chains into the final list.

A dummy head node is used for splitting and merging. It removes special cases for empty lists and the first node, since the real head can always be replaced by dummy.next.

Algorithm and Walkthrough

Consider:

1 -> 8 -> 3 -> 6 -> 5 -> 4 -> None

Stage Result
Original list 1 -> 8 -> 3 -> 6 -> 5 -> 4 -> None
Odd positions 1 -> 3 -> 5 -> None
Even positions 8 -> 6 -> 4 -> None
Reverse even positions 4 -> 6 -> 8 -> None
Merge both chains 1 -> 3 -> 4 -> 5 -> 6 -> 8 -> None

The merge compares the first node of each chain and repeatedly attaches the smaller node to the result.

Complexity

  • Best case: O(n), because splitting, reversing, and merging each require one traversal.

  • Average case: O(n).

  • Worst case: O(n).

  • Auxiliary space: O(1), excluding the input list. The algorithm reuses the existing nodes, creates only a constant number of dummy and pointer variables, and uses no recursion. Including the input list, total storage is O(n).

Linked Lists vs Arrays

Operation Array Linked List
Access by index O(1) O(n)
Insert or delete at a known position O(n), due to shifting O(1), with the previous node
Insert or delete at the head O(n), due to shifting O(1)
Store n values O(n) O(n)

Linked lists therefore support efficient structural changes, but locating a value by index requires traversal.

Code Example

from __future__ import annotations


class ListNode:
    def __init__(self, val: int, next: ListNode | None = None) -> None:
        self.val = val
        self.next = next


def sort_alternating_list(head: ListNode | None) -> ListNode | None:
    """Sort odd-positioned ascending and even-positioned descending nodes."""
    odd_dummy = ListNode(0)
    even_dummy = ListNode(0)
    odd_tail = odd_dummy
    even_tail = even_dummy

    # Split the list into odd-position and even-position chains.
    current = head
    is_odd = True

    while current is not None:
        next_node = current.next
        current.next = None

        if is_odd:
            odd_tail.next = current
            odd_tail = current
        else:
            even_tail.next = current
            even_tail = current

        current = next_node
        is_odd = not is_odd

    # Reverse the descending even-position chain using prev/curr/next.
    previous: ListNode | None = None
    current = even_dummy.next

    while current is not None:
        next_node = current.next
        current.next = previous
        previous = current
        current = next_node

    # Merge the two ascending chains.
    merged_dummy = ListNode(0)
    tail = merged_dummy
    left = odd_dummy.next
    right = previous

    while left is not None and right is not None:
        if left.val <= right.val:
            tail.next = left
            left = left.next
        else:
            tail.next = right
            right = right.next

        tail = tail.next

    tail.next = left if left is not None else right

    result = merged_dummy.next
    merged_dummy.next = None
    return result


head = ListNode(
    1,
    ListNode(8, ListNode(3, ListNode(6, ListNode(5, ListNode(4))))),
)

sorted_head = sort_alternating_list(head)

values = []
current = sorted_head
while current is not None:
    values.append(current.val)
    current = current.next

print(values)  # [1, 3, 4, 5, 6, 8]

Common Pitfalls

  • Position numbering: The first node is position 1 in this algorithm. Using a different convention produces incorrect chains.

  • Input mutation: The function rearranges the existing nodes rather than creating a copy.

  • Duplicate values: The chains are nondecreasing and nonincreasing, so duplicates are valid; using <= keeps the merge deterministic.

  • Edge cases: Empty input returns None, and a one-node list is returned unchanged. Negative values require no special handling.

  • Terminology: This algorithm assumes odd-positioned nodes are ascending and even-positioned nodes are descending. If “alternating” instead means a local zigzag such as a <= b >= c <= d, the subsequences are not necessarily sorted; use a general linked-list merge sort with O(n log n) time instead.

  • Interview follow-ups: Common questions include reversing every second node, merging two sorted lists, and validating whether a list satisfies the alternating-order precondition.

52

How do you swap adjacent node pairs in a linked list?

A pair-wise node swap reverses every two adjacent nodes by rewiring their next pointers. A dummy head simplifies handling the first pair and boundary cases, while an odd final node remains unchanged.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

Use a dummy (sentinel) head so the first pair is processed exactly like every other pair. Maintain:

  • previous: the node before the pair being swapped.

  • current: the first node in the pair.

  • second: the second node in the pair.

For each complete pair, rewire the links from:

previous -> first -> second -> remainder

to:

previous -> second -> first -> remainder

Then move previous to first, the first node of the completed pair. This implementation swaps the actual nodes and their links rather than merely exchanging their val fields.

For example:

Before: 1 -> 2 -> 3 -> 4 -> None
After:  2 -> 1 -> 4 -> 3 -> None

With an odd number of nodes, the last node is not paired:

Before: 1 -> 2 -> 3 -> None
After:  2 -> 1 -> 3 -> None

Step-by-Step Walkthrough

Consider the list 1 -> 2 -> 3 -> 4 -> None. The algorithm proceeds as follows:

  1. Initial state: dummy_head -> 1 -> 2 -> 3 -> 4 -> None, previous = dummy_head, current = 1.

  2. First pair (1, 2):

  3. first = 1, second = 2.

  4. Rewire: first.next = 3, second.next = 1, previous.next = 2.

  5. List becomes: dummy_head -> 2 -> 1 -> 3 -> 4 -> None.

  6. Update: previous = 1, current = 3.

  7. Second pair (3, 4):

  8. first = 3, second = 4.

  9. Rewire: first.next = None, second.next = 3, previous.next = 4.

  10. List becomes: dummy_head -> 2 -> 1 -> 4 -> 3 -> None.

  11. Update: previous = 3, current = None.

  12. Loop ends because current is None. Return dummy_head.next which points to 2.

Complexity

Case Time Reason
Best O(n) The list must be traversed to find all pairs and the tail.
Average O(n) The same linear traversal is required.
Worst O(n) Every node is visited once.
  • Auxiliary space: O(1), excluding the input list; only a fixed number of pointers and one sentinel node are used.

  • Total space including the input: O(n).

  • Recursion stack: O(1), because the implementation is iterative.

Linked List Compared with an Array

Operation Linked list Array
Access by position O(n) O(1)
Insert after a known node O(1) O(n) because elements may shift
Delete after a known node O(1) O(n) because elements may shift
Swap adjacent pairs O(n) O(n)

The linked list performs each local rewiring in O(1), but finding the nodes to swap still requires an O(n) traversal.

Code Example

from __future__ import annotations


class ListNode:
    def __init__(self, val: int, next: ListNode | None = None) -> None:
        self.val = val
        self.next = next


def swap_pairs(head: ListNode | None) -> ListNode | None:
    """Swap every pair of adjacent nodes and return the new head."""
    dummy_head = ListNode(0, head)
    previous = dummy_head
    current = head

    while current is not None and current.next is not None:
        first = current
        second = current.next

        # Rewire the pair: previous -> second -> first -> remainder.
        first.next = second.next
        second.next = first
        previous.next = second

        # The first node is now the tail of the swapped pair.
        previous = first
        current = first.next

    return dummy_head.next


def list_values(head: ListNode | None) -> list[int]:
    values: list[int] = []
    current = head

    while current is not None:
        values.append(current.val)
        current = current.next

    return values


head = ListNode(1, ListNode(2, ListNode(3, ListNode(4))))
result = swap_pairs(head)
print(list_values(result))  # Expected output: [2, 1, 4, 3]

Common Pitfalls

  • Forgetting the odd-length case: When only one node remains, leave it linked to the previous result without attempting a swap.

  • Moving the wrong pointer: After swapping a pair, previous must point to the first node of that pair, not the second.

  • Losing the remainder: Save second.next before changing first.next.

  • Swapping values when nodes are required: Exchanging val is simpler, but it does not meet requirements that explicitly ask to swap nodes.

  • Mutating the input: This algorithm intentionally rewires the original list in place. Clone the nodes first if the caller must retain the original structure.

  • Common follow-up questions: Explain how to handle an odd-length list, reverse alternating pairs, or adapt the algorithm to a doubly linked list.

53

How do you remove odd-indexed nodes from a linked list?

Remove nodes whose zero-based indices are 1, 3, 5, ..., while preserving nodes at indices 0, 2, 4, .... A dummy head simplifies removal by keeping a pointer to the last retained node, allowing every deletion to use the same pattern.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Indexing and Approach

  • Treat the head node as index 0.

  • Traverse the list with current and track index.

  • Keep a pointer named prev to the last retained node.

  • When index is odd, bypass the current node with prev.next = current.next.

  • When index is even, advance prev to the current node.

  • Return dummy.next because the dummy node itself must not be part of the result.

Using a dummy head avoids separate logic for removing the first node, even though an odd-index removal never removes index 0 directly.

Code Example

from __future__ import annotations


class ListNode:
    def __init__(self, val: int, next: ListNode | None = None) -> None:
        self.val = val
        self.next = next


def remove_odd_indexed_nodes(head: ListNode | None) -> ListNode | None:
    """Remove nodes at odd zero-based indices from a singly linked list."""
    dummy = ListNode(0, head)
    prev = dummy
    current = head
    index = 0

    while current is not None:
        next_node = current.next

        if index % 2 == 1:
            # Bypass this node because its index is odd.
            prev.next = next_node
        else:
            # Retain this node and move prev forward.
            prev = current

        current = next_node
        index += 1

    return dummy.next


# Example call
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
result = remove_odd_indexed_nodes(head)

values: list[int] = []
current = result
while current is not None:
    values.append(current.val)
    current = current.next

print(values)  # Expected output: [1, 3, 5]

Walkthrough

For the list:

1 -> 2 -> 3 -> 4 -> 5 -> None

Index Node Action Resulting retained sequence
0 1 Keep 1
1 2 Remove 1
2 3 Keep 1 -> 3
3 4 Remove 1 -> 3
4 5 Keep 1 -> 3 -> 5

Final list:

1 -> 3 -> 5 -> None

The algorithm modifies the original list in place and returns its new head.

Comparison with Arrays

Operation Linked List Array
Access by index O(n) O(1)
Insert/delete at known node O(1) O(n)

Linked lists trade fast random access for O(1) insertion/deletion when the target node is already located, whereas arrays require shifting elements.

Complexity

  • Best case: O(n) — every node must be visited to determine its index.

  • Average case: O(n) — traversal visits each node once.

  • Worst case: O(n) — traversal visits each node once.

  • Auxiliary space: O(1) — only dummy, prev, current, next_node, and index are used; there is no recursion stack.

  • Space including the linked list: O(n) because the input list is mutated and reused as the output.

Edge Cases

  • Empty list: Returns None.

  • One element: Keeps the element because it is at index 0.

  • Two elements: Keeps only the first element.

  • Duplicate or negative values: Removal depends only on position, not value.

  • Already ordered values: Ordering does not affect the algorithm.

  • Cyclic list: This implementation assumes the list terminates; cycle detection must be added if cyclic input is possible.

Common Pitfalls

  • Using one-based instead of zero-based indexing changes which nodes are removed.

  • Forgetting to save current.next before bypassing a node.

  • Advancing prev after removing a node, which would retain an unwanted node.

  • Assuming head must change; with zero-based indexing, the original head at index 0 is always retained.

  • Using recursion unnecessarily; an iterative traversal avoids Python’s recursion-depth limit.

  • Interviewers may follow up by asking for the inverse operation, cycle detection, or removal by value.

54

How can reservoir sampling uniformly select a node from a linked list?

Use reservoir sampling with a reservoir of size one. Traverse the list while maintaining one selected node, replacing it with the current node with probability 1 / k, where k is the number of nodes seen so far.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

For each node in the linked list:

  1. Increment the number of nodes processed, k.

  2. Generate a random integer from 0 through k - 1.

  3. Replace the currently selected node if that integer is 0.

The replacement probability at step k is therefore 1 / k. For example, while processing 1 -> 2 -> 3 -> None, the selection probabilities are:

Node processed Probability of replacing the selection
1 1
2 1 / 2
3 1 / 3

A dummy sentinel head provides a stable starting point and avoids special handling for the first actual node. It does not modify the input list.

Why Selection Is Uniform

Assume the selected node is uniform among the first k - 1 nodes. When the kth node arrives:

  • The new node is selected with probability 1 / k.

  • Each previous node remains selected with probability 1 - 1 / k.

  • Each previous node’s final selection probability is 1 / (k - 1) × (k - 1) / k = 1 / k.

Thus, every node among the first k nodes has probability 1 / k. After the entire list is processed, every node has probability 1 / n.

Complexity

  • Best-case time: O(n) because every node must be visited.

  • Average-case time: O(n) because the list is traversed exactly once.

  • Worst-case time: O(n) because replacing the selected node does not affect traversal time.

  • Auxiliary space: O(1), including the constant-sized call stack. The input list occupies O(n) space and is not counted as auxiliary space; total space including the input is O(n).

Linked Lists vs Arrays

Operation Array Linked List
Access by index O(1) O(n)
Insert or delete at a known position O(n) due to shifting O(n) to locate the position
Insert or delete when the node is already known O(n) for an array slot O(1) with the previous node
Uniform random selection O(1) by choosing an index O(n) with reservoir sampling

Code Example

from __future__ import annotations

import random
from collections.abc import Callable


class ListNode:
    def __init__(self, val: int, next: ListNode | None = None) -> None:
        self.val = val
        self.next = next


def select_random_node(
    head: ListNode | None,
    random_source: Callable[[int], int] = random.randrange,
) -> ListNode | None:
    """Select a node uniformly using reservoir sampling."""
    dummy_head = ListNode(0, head)
    current = dummy_head.next
    selected: ListNode | None = None
    node_count = 0

    while current is not None:
        node_count += 1

        # random_source(node_count) returns an integer in [0, node_count - 1].
        if random_source(node_count) == 0:
            selected = current

        current = current.next

    return selected


head = ListNode(1, ListNode(2, ListNode(3)))
selected = select_random_node(head, random_source=lambda upper: 0)

assert selected is not None
print(selected.val)  # Expected output: 3

# Before: 1 -> 2 -> 3 -> None
# After:  1 -> 2 -> 3 -> None

In production, omit random_source so random.randrange provides the required randomness.

Common Pitfalls

  • Empty list: The function returns None without entering the traversal loop.

  • Single node: That node is always selected.

  • Duplicate values: Uniformity applies to nodes, not distinct values; duplicate-valued nodes remain separate candidates.

  • Negative values: Values do not affect selection.

  • Pre-sorted input: Ordering is irrelevant because the algorithm treats every node equally.

  • Cycles: The algorithm assumes a finite, acyclic list. A cyclic list would cause an infinite traversal unless the cycle is detected separately.

  • Biased implementation: Choosing only among the first few nodes, or replacing the selection with a fixed probability, does not produce uniform sampling.

  • Input mutation: The sentinel is temporary, and the original list remains unchanged.

55

How do you copy a linked list with random pointers?

A linked list with random pointers can be deep-copied using two passes: first create every copied node and record an identity mapping, then connect the next and random references. The mapping is essential because random pointers may target any node, including the node itself.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

  1. Traverse the original list and create a clone of each node.

  2. Store each original node and its clone in a dictionary, using node identity rather than val.

  3. Traverse the mapped nodes again:

  4. Point each clone’s next to the clone of the original next.

  5. Point each clone’s random to the clone of the original random.

  6. Return the copied head.

A dummy head node simplifies the implementation: the cloned head is always attached to dummy_head.next, and an empty list naturally returns None.

Original state:

1 -> 2 -> 3 -> None
1.random -> 3, 2.random -> 1, 3.random -> None

Copied state:

1' -> 2' -> 3' -> None
1'.random -> 3', 2'.random -> 1', 3'.random -> None

Complexity

Let n be the number of distinct nodes.

  • Best-case time: O(n), because every node must be cloned.

  • Average/expected time: O(n), because dictionary insertion and lookup take O(1) on average.

  • Worst-case time: O(n²) under pathological dictionary hash collisions; expected hashing gives O(n) total time.

  • Auxiliary space: O(n) for the node-to-node dictionary.

  • Output space: O(n) for the copied list.

  • The original input is not counted, and the iterative implementation uses no recursion stack.

Linked Lists vs Arrays

Operation Linked list with random pointer Array
Access by position O(n) O(1)
Access through next or random O(1) O(1)
Insert after a known node and predecessor O(1) O(n)
Delete a known node and predecessor O(1) O(n)

Code Example

from __future__ import annotations

from dataclasses import dataclass


@dataclass(eq=False)
class ListNode:
    val: int
    next: ListNode | None = None
    random: ListNode | None = None


def copy_list_with_random(head: ListNode | None) -> ListNode | None:
    """Return a deep copy of a linked list, including random pointers."""
    dummy_head = ListNode(0)
    clones: dict[ListNode, ListNode] = {}

    # First pass: clone every node reachable through next.
    current = head
    tail = dummy_head

    while current is not None and current not in clones:
        clone = ListNode(current.val)
        clones[current] = clone
        tail.next = clone
        tail = clone
        current = current.next

    # Second pass: connect copied next and random pointers.
    for original, clone in clones.items():
        clone.next = None if original.next is None else clones[original.next]
        clone.random = (
            None if original.random is None else clones[original.random]
        )

    return dummy_head.next


if __name__ == "__main__":
    first = ListNode(1)
    second = ListNode(2)
    third = ListNode(3)

    first.next = second
    second.next = third
    first.random = third
    second.random = first
    third.random = None

    copied = copy_list_with_random(first)

    values: list[int] = []
    random_values: list[int | None] = []
    current = copied

    while current is not None:
        values.append(current.val)
        random_values.append(
            current.random.val if current.random is not None else None
        )
        current = current.next

    print(f"values={values}, random={random_values}")
    # Expected: values=[1, 2, 3], random=[3, 1, None]

Common Pitfalls

  • Shallow copying: Reusing original nodes means changing the copy also changes the original. This implementation does not mutate the input list.

  • Mapping by value: The dictionary must use node identity, not val; duplicate values must remain separate nodes. In Python, eq=False prevents the dataclass from becoming unhashable.

  • Premature pointer resolution: Create all clones before resolving copied random targets, because a target may not have been visited yet. The mapping also serves as the visited set.

  • Off-by-one errors: Verify that dummy_head.next is returned and that each cloned next pointer advances by exactly one node.

  • Integer overflow: Python integers do not overflow; implementations using fixed-width integer types must ensure counters and index calculations cannot overflow.

  • Edge cases: Empty lists return None; one-node lists, duplicate and negative values, self-referencing random pointers, and random-pointer cycles are supported. Sorted input and disconnected graphs are not meaningful distinctions for this operation.

  • Invalid targets: A random pointer to a node outside the list violates the contract and causes a KeyError.

  • Recursion depth: Prefer the iterative implementation because a recursive solution can exceed Python’s default recursion limit for more than roughly 1,000 nodes.

  • Follow-up question: Interviewers may ask for an O(1)-auxiliary-space solution that interleaves cloned nodes with the originals and then separates the two lists.

Sign in to keep reading

You've opened 2 full answers. Sign in to read all 55 Linked Lists answers, mark what you know and pick up where you left off.

Report a mistake

What's wrong?

All Data Structures & Algorithms subjects