🦄 Tailflip: Reverse Singly Linked List

Difficulty: Intermediate Tags: linked-list, pointers, iteration, in-place Series: Data Structures I

Problem

The Tailflip reverses the magical chain of unicorn connections. Reverse a singly linked list in-place by rewiring the next pointers.

Given a singly linked list represented as an array of nodes, reverse it in-place and return the modified array with the new head index.

Node Representation: - Each node: [value, next_index] - next_index = -1 means null (end of list) - Nodes array contains all nodes (may be unordered) - Head index points to the first node in the list

In-Place Reversal: - Modify the next pointers in the nodes array - Don't create new nodes, rewire existing ones - Return same nodes array with updated pointers

Real-World Application

Linked list reversal is fundamental in: - Undo/Redo stacks - reversing operation history - Memory management - reversing free list order - Network packet processing - reordering packet chains - Text editors - reversing character sequences - Graph algorithms - reversing adjacency lists - Database systems - reversing linked record chains - Operating systems - reversing process queues - Compiler design - reversing syntax tree branches

Input

data = {
    'nodes': List[List[int, int]],  # [[value, next_idx], ...]
    'head': int  # Index of head node (-1 for empty list)
}

Output

{
    'nodes': List[List[int, int]],  # Modified nodes array
    'head': int  # Index of new head after reversal
}

Constraints

• 0 ≤ number of nodes ≤ 100,000
• Node values are integers
• -1 represents null pointer
• Nodes in array may not be in list order
• Must reverse in-place (modify existing array)

Examples

Example 1: Three Nodes

Input:

{
    'nodes': [[1, 1], [2, 2], [3, -1]],
    'head': 0
}

Original List: 1 → 2 → 3 - Node 0: value=1, next=1 (points to node 1) - Node 1: value=2, next=2 (points to node 2) - Node 2: value=3, next=-1 (end)

Output:

{
    'nodes': [[1, -1], [2, 0], [3, 1]],
    'head': 2
}

Reversed List: 3 → 2 → 1 - Node 2: value=3, next=1 (new head) - Node 1: value=2, next=0 - Node 0: value=1, next=-1 (new tail)

Example 2: Empty List

Input:

{
    'nodes': [],
    'head': -1
}

Output:

{
    'nodes': [],
    'head': -1
}

Explanation: Empty list remains empty.

Example 3: Single Node

Input:

{
    'nodes': [[42, -1]],
    'head': 0
}

Output:

{
    'nodes': [[42, -1]],
    'head': 0
}

Explanation: Single node list is unchanged (already reversed).

Example 4: Two Nodes

Input:

{
    'nodes': [[1, 1], [2, -1]],
    'head': 0
}

Original: 1 → 2

Output:

{
    'nodes': [[1, -1], [2, 0]],
    'head': 1
}

Reversed: 2 → 1

Example 5: Longer List

Input:

{
    'nodes': [[1, 1], [2, 2], [3, 3], [4, 4], [5, -1]],
    'head': 0
}

Original: 1 → 2 → 3 → 4 → 5

Output:

{
    'nodes': [[1, -1], [2, 0], [3, 1], [4, 2], [5, 3]],
    'head': 4
}

Reversed: 5 → 4 → 3 → 2 → 1

What You'll Learn

• Linked list pointer manipulation
• In-place reversal algorithm
• Working with indices as pointers
• Three-pointer technique
• Iterative vs recursive reversal

Why This Matters

Linked list reversal is the #2 most common linked list interview question: - Tests understanding of pointer manipulation - Requires careful state tracking - Demonstrates in-place algorithm skills - Foundation for more complex list operations

Companies that ask this: Google, Amazon, Microsoft, Facebook, Apple, Bloomberg, LinkedIn

Starter Code

def challenge_function(data):
    """
    Reverse a singly linked list in-place.

    Args:
        data: dict with keys:
            - 'nodes' (List[List[int, int]]): array of [value, next_index]
              where -1 means null
            - 'head' (int): index of head node (-1 for empty list)

    Returns:
        dict with keys:
            - 'nodes' (List[List[int, int]]): modified nodes array
            - 'head' (int): index of new head after reversal
    """
    # Your implementation here
    pass