Advanced

LinkedList Advanced

Five hard linked list problems frequently asked at top tech companies. These require combining multiple techniques: reversal, hash maps, recursion, and careful pointer manipulation.

Problem 1: Reverse Nodes in K-Group (LC 25)

Problem: Given a linked list, reverse the nodes k at a time and return the modified list. Nodes that are left out (less than k) stay in original order.

# Input:  1 -> 2 -> 3 -> 4 -> 5, k = 3
# Output: 3 -> 2 -> 1 -> 4 -> 5
#
# Group 1: [1, 2, 3] -> reverse -> [3, 2, 1]
# Group 2: [4, 5]    -> only 2 nodes, k=3, keep as-is
#
# Diagram:
#   Before: dummy -> [1 -> 2 -> 3] -> [4 -> 5] -> None
#   After:  dummy -> [3 -> 2 -> 1] -> [4 -> 5] -> None
#                     reversed         unchanged

def reverseKGroup(head, k):
    """Reverse nodes in groups of k.

    Strategy:
    1. Count if there are k nodes remaining
    2. If yes, reverse k nodes
    3. Recursively handle the rest
    4. Connect the reversed group to the result

    Time:  O(n) - each node visited twice (count + reverse)
    Space: O(n/k) - recursion depth
    """
    # Check if there are at least k nodes
    count = 0
    node = head
    while node and count < k:
        node = node.next
        count += 1

    if count < k:
        return head  # not enough nodes, keep as-is

    # Reverse k nodes
    prev = None
    curr = head
    for _ in range(k):
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node

    # head is now the tail of reversed group
    # curr is the start of the next group
    head.next = reverseKGroup(curr, k)

    return prev  # new head of this group

Problem 2: Copy List with Random Pointer (LC 138)

Problem: A linked list where each node has a next pointer and a random pointer (which can point to any node or null). Create a deep copy.

# Original list with random pointers:
#
#   Node1 -> Node2 -> Node3 -> None
#     |        |        |
#     v        v        v
#   Node3    Node1     None    (random pointers)
#
# Deep copy: create entirely new nodes with same structure

class Node:
    def __init__(self, val=0, next=None, random=None):
        self.val = val
        self.next = next
        self.random = random


def copyRandomList(head):
    """Deep copy a linked list with random pointers.

    Strategy: Use a hash map to map original -> copy nodes.
    Two passes:
      Pass 1: Create all copy nodes (without connections)
      Pass 2: Set next and random pointers using the map

    Time:  O(n) - two passes
    Space: O(n) - hash map for node mapping
    """
    if not head:
        return None

    # Pass 1: Create copy nodes
    old_to_new = {}
    curr = head
    while curr:
        old_to_new[curr] = Node(curr.val)
        curr = curr.next

    # Pass 2: Set pointers
    curr = head
    while curr:
        copy = old_to_new[curr]
        copy.next = old_to_new.get(curr.next)
        copy.random = old_to_new.get(curr.random)
        curr = curr.next

    return old_to_new[head]


def copyRandomList_O1_space(head):
    """Deep copy with O(1) extra space (interleaving method).

    Step 1: Insert copy nodes: A -> A' -> B -> B' -> C -> C'
    Step 2: Set random pointers using interleaved structure
    Step 3: Separate the two lists

    Time:  O(n)
    Space: O(1) - no hash map needed
    """
    if not head:
        return None

    # Step 1: Interleave copy nodes
    curr = head
    while curr:
        copy = Node(curr.val)
        copy.next = curr.next
        curr.next = copy
        curr = copy.next

    # Step 2: Set random pointers
    curr = head
    while curr:
        if curr.random:
            curr.next.random = curr.random.next
        curr = curr.next.next

    # Step 3: Separate lists
    curr = head
    copy_head = head.next
    while curr:
        copy = curr.next
        curr.next = copy.next
        copy.next = copy.next.next if copy.next else None
        curr = curr.next

    return copy_head

Problem 3: Flatten a Multilevel Doubly Linked List (LC 430)

Problem: Flatten a multilevel doubly linked list where some nodes have a child pointer to another doubly linked list.

# Input (multilevel):
#
#  1 --- 2 --- 3 --- 4 --- 5 --- 6
#              |
#              7 --- 8 --- 9 --- 10
#                    |
#                    11 --- 12
#
# Output (flattened):
#  1 - 2 - 3 - 7 - 8 - 11 - 12 - 9 - 10 - 4 - 5 - 6
#
# Rule: When a child list exists, insert it between
#       the current node and its next node.

def flatten(head):
    """Flatten multilevel doubly linked list.

    Strategy: Use a stack to handle child lists.
    When we encounter a child, push the next node onto
    the stack and process the child list first.

    Time:  O(n) - visit each node once
    Space: O(d) - stack depth = number of nesting levels
    """
    if not head:
        return head

    dummy = DListNode(0)
    dummy.next = head
    prev = dummy
    stack = [head]

    while stack:
        curr = stack.pop()

        # Connect prev to curr
        prev.next = curr
        curr.prev = prev

        # If curr has next, save it for later
        if curr.next:
            stack.append(curr.next)

        # If curr has child, process child first (push on top)
        if hasattr(curr, 'child') and curr.child:
            stack.append(curr.child)
            curr.child = None  # remove child pointer

        prev = curr

    # Detach dummy
    dummy.next.prev = None
    return dummy.next

Problem 4: Add Two Numbers (LC 2)

Problem: Two non-negative integers are stored as linked lists in reverse order. Each node contains a single digit. Add the two numbers and return the sum as a linked list.

# Input:  l1 = 2 -> 4 -> 3  (represents 342)
#         l2 = 5 -> 6 -> 4  (represents 465)
# Output: 7 -> 0 -> 8       (represents 807)
#
# Addition with carry:
#
#   2 + 5 = 7,  carry = 0  -> node 7
#   4 + 6 = 10, carry = 1  -> node 0
#   3 + 4 + 1(carry) = 8   -> node 8
#
# Result: 7 -> 0 -> 8 (807)

def addTwoNumbers(l1, l2):
    """Add two numbers represented as reversed linked lists.

    Process digit by digit from least significant (head).
    Track carry for sums >= 10.

    Time:  O(max(n, m)) - traverse both lists
    Space: O(max(n, m)) - result list length
    """
    dummy = ListNode(0)
    curr = dummy
    carry = 0

    while l1 or l2 or carry:
        # Get current digits (0 if list is exhausted)
        val1 = l1.val if l1 else 0
        val2 = l2.val if l2 else 0

        # Calculate sum and carry
        total = val1 + val2 + carry
        carry = total // 10
        digit = total % 10

        # Create new node
        curr.next = ListNode(digit)
        curr = curr.next

        # Advance pointers
        l1 = l1.next if l1 else None
        l2 = l2.next if l2 else None

    return dummy.next

Problem 5: Reorder List (LC 143)

Problem: Given L0 → L1 → ... → Ln-1 → Ln, reorder to L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → ...

# Input:  1 -> 2 -> 3 -> 4 -> 5
# Output: 1 -> 5 -> 2 -> 4 -> 3
#
# Strategy: Three steps
#
# Step 1: Find middle using slow/fast
#   1 -> 2 -> 3 -> 4 -> 5
#              ^
#            middle
#
# Step 2: Reverse the second half
#   First half:  1 -> 2 -> 3
#   Second half: 5 -> 4  (reversed)
#
# Step 3: Merge alternately
#   1 -> 5 -> 2 -> 4 -> 3

def reorderList(head):
    """Reorder list by interleaving front and reversed back.

    Combines three fundamental techniques:
    1. Find middle (slow/fast pointer)
    2. Reverse linked list
    3. Merge two lists

    Time:  O(n) - three O(n) passes
    Space: O(1) - in-place pointer manipulation
    """
    if not head or not head.next:
        return

    # Step 1: Find middle
    slow = fast = head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next

    # Step 2: Reverse second half
    prev = None
    curr = slow.next
    slow.next = None  # cut the list

    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node

    # Step 3: Merge two halves
    first, second = head, prev
    while second:
        tmp1, tmp2 = first.next, second.next
        first.next = second
        second.next = tmp1
        first = tmp1
        second = tmp2

Complexity Summary

Problem	Time	Space	Key Technique
Reverse K-Group	O(n)	O(n/k)	Count + reverse in groups
Copy Random Pointer	O(n)	O(n) or O(1)	Hash map or interleaving
Flatten Multilevel	O(n)	O(d)	Stack-based DFS
Add Two Numbers	O(max(n,m))	O(max(n,m))	Digit-by-digit with carry
Reorder List	O(n)	O(1)	Middle + reverse + merge