Linked List

Given the head of a singly linked list, reverse the list and return the reversed list.

Iterate through the list while keeping two pointers: prev (the already reversed part, initially None) and curr (the current node). At each step, save curr.next, point curr.next back to prev, then advance both pointers. When curr becomes None, prev is the new head. This is preferred over recursion because it uses constant space and avoids stack overflow on long lists.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

def reverseList(head: Optional[ListNode]) -> Optional[ListNode]:
    prev, curr = None, head
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev
    

Given the heads of two sorted linked lists list1 and list2, merge them into one sorted list by splicing together the nodes of the two lists, and return the head of the merged list.

Use a dummy node and a tail pointer to build the result. Compare the heads of both lists, attach the smaller node to tail, and advance that list. When one list is exhausted, attach the remainder of the other list directly, since it is already sorted. Reusing the existing nodes keeps extra space constant, and the dummy node removes special handling for the head.

def mergeTwoLists(list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
    dummy = ListNode()
    tail = dummy
    while list1 and list2:
        if list1.val <= list2.val:
            tail.next = list1
            list1 = list1.next
        else:
            tail.next = list2
            list2 = list2.next
        tail = tail.next
    tail.next = list1 or list2
    return dummy.next
    

Given the head of a singly linked list L0 → L1 → ... → Ln-1 → Ln, reorder it to L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → ... in-place, without modifying node values.

Combine three standard linked list techniques. First, find the middle using slow and fast pointers. Second, cut the list in two and reverse the second half. Third, merge the two halves by alternating nodes (one from the first half, one from the reversed second half). Using a different technique per step avoids the \(O(N)\) extra space of storing nodes in an array.

def reorderList(head: Optional[ListNode]) -> None:
    # 1. Find the middle
    slow, fast = head, head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    # 2. Split and reverse the second half
    second = slow.next
    slow.next = None
    prev = None
    while second:
        nxt = second.next
        second.next = prev
        prev = second
        second = nxt

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

Given the head of a linked list, remove the n-th node from the end of the list and return its head.

Use the Two Pointers technique with a fixed gap in a single pass. Start both pointers at a dummy node placed before head. Move fast ahead by n + 1 steps, then move both pointers together until fast reaches None. At that point slow sits right before the node to delete, so skip it with slow.next = slow.next.next. The dummy node handles the case where the head itself is removed.

def removeNthFromEnd(head: Optional[ListNode], n: int) -> Optional[ListNode]:
    dummy = ListNode(0, head)
    slow = fast = dummy

    # Create a gap of n nodes between slow and fast
    for _ in range(n + 1):
        fast = fast.next

    while fast:
        slow = slow.next
        fast = fast.next

    slow.next = slow.next.next
    return dummy.next
    

Given head, the head of a linked list, determine if the linked list has a cycle in it. Return True if there is a cycle, otherwise return False.

Floyd's Tortoise and Hare: Move slow one step and fast two steps at a time. If the list has a cycle, fast eventually laps slow and they meet at the same node. If fast reaches None, the list ends and there is no cycle. A hash set of visited nodes also works but costs \(O(N)\) space.

def hasCycle(head: Optional[ListNode]) -> bool:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False
    

You are given an array of k linked lists lists, each sorted in ascending order. Merge all the linked lists into one sorted linked list and return it.

Use a Min-Heap holding the current head of each list. Repeatedly pop the smallest node, append it to the result, and push that node's next into the heap. The heap never holds more than k nodes, so each of the \(N\) total nodes costs \(O(\log k)\). Since ListNode objects are not comparable, store tuples (value, list_index, node) so ties are broken by the unique index. An equivalent alternative is divide and conquer, merging lists pairwise with the Problem 22 routine, which also runs in \(O(N \log k)\).

import heapq

def mergeKLists(lists: list[Optional[ListNode]]) -> Optional[ListNode]:
    heap = []
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))

    dummy = ListNode()
    tail = dummy
    while heap:
        val, i, node = heapq.heappop(heap)
        tail.next = node
        tail = tail.next
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
    return dummy.next
    

Design a data structure that follows the Least Recently Used (LRU) cache policy. Implement LRUCache(capacity), get(key) (return the value or -1) and put(key, value) (insert or update, evicting the least recently used key when capacity is exceeded). Both operations must run in \(O(1)\) average time.

Combine a Hash Map with a Doubly Linked List. The hash map gives \(O(1)\) access from a key to its node, and the doubly linked list keeps nodes ordered by recency: the node after the left sentinel is the least recently used, and the node before the right sentinel is the most recently used. Because each node has prev and next pointers, removing it from any position and re-inserting it at the most-recent end is \(O(1)\). Two sentinel nodes remove all edge cases at the ends. In Python, collections.OrderedDict gives the same behavior in fewer lines, but this manual version shows the underlying design.

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

class LRUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.cache = {}  # key -> Node
        # Sentinels: left.next is the LRU node, right.prev is the MRU node
        self.left, self.right = Node(), Node()
        self.left.next = self.right
        self.right.prev = self.left

    def _remove(self, node: Node) -> None:
        prev, nxt = node.prev, node.next
        prev.next = nxt
        nxt.prev = prev

    def _insert(self, node: Node) -> None:
        # Insert just before the right sentinel (most recently used)
        prev = self.right.prev
        prev.next = node
        node.prev = prev
        node.next = self.right
        self.right.prev = node

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self._remove(node)
        self._insert(node)
        return node.val

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self._remove(self.cache[key])
        self.cache[key] = Node(key, value)
        self._insert(self.cache[key])

        if len(self.cache) > self.cap:
            lru = self.left.next
            self._remove(lru)
            del self.cache[lru.key]
    

Given the head of a linked list, reverse the nodes of the list k at a time and return the modified list. If the number of remaining nodes is not a multiple of k, the left-out nodes at the end stay as they are. Only the nodes themselves may be changed, not their values.

Process the list group by group using a dummy node and a group_prev pointer that sits right before the current group. For each group, find the k-th node (kth); if it does not exist, fewer than k nodes remain, so stop. Otherwise reverse the group with the standard reversal, but initialize prev to kth.next so the reversed group links to the rest of the list automatically. Finally reconnect group_prev to kth and move it to the old first node of the group, which is now the group's tail. Each node is visited a constant number of times, and the iterative approach avoids \(O(N/k)\) recursion stack space.

def reverseKGroup(head: Optional[ListNode], k: int) -> Optional[ListNode]:
    def getKth(curr, k):
        while curr and k > 0:
            curr = curr.next
            k -= 1
        return curr

    dummy = ListNode(0, head)
    group_prev = dummy

    while True:
        kth = getKth(group_prev, k)
        if not kth:
            break
        group_next = kth.next

        # Reverse the group; prev starts at group_next to link the tail
        prev, curr = group_next, group_prev.next
        while curr != group_next:
            tmp = curr.next
            curr.next = prev
            prev = curr
            curr = tmp

        # Reconnect: old first node is now the group's tail
        tmp = group_prev.next
        group_prev.next = kth
        group_prev = tmp

    return dummy.next