Linked List

Key techniques: dummy head node (avoids edge cases), fast/slow pointers (cycle detection, find middle), two-pass technique (remove nth from end).

Easy Reverse Linked List

INSIGHT: Three pointers: prev, curr, next. Save next before overwriting curr.next.

def reverseList(head):
    prev, curr = None, head
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev
# Time: O(n) | Space: O(1)

# Recursive version:
def reverseList(head):
    if not head or not head.next: return head
    new_head = reverseList(head.next)
    head.next.next = head
    head.next = None
    return new_head

Easy Linked List Cycle (Floyd's)

INSIGHT: Fast pointer moves 2x. If a cycle exists, fast will eventually lap slow. They'll meet inside the cycle.

def hasCycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False
# Time: O(n) | Space: O(1)

Medium Remove Nth Node From End

INSIGHT: Dummy node + two pointers. Advance right pointer n steps, then move both until right hits end. Left.next is the node to remove.

def removeNthFromEnd(head, n):
    dummy = ListNode(0, head)
    l, r = dummy, head
    for _ in range(n): r = r.next
    while r:
        l = l.next; r = r.next
    l.next = l.next.next
    return dummy.next
# Time: O(n) | Space: O(1) — one pass!

Hard LRU Cache ⭐ (SDE 2 Favourite)

INSIGHT: HashMap (O(1) lookup) + Doubly Linked List (O(1) insertion/deletion). Head = LRU, Tail = MRU. Use dummy head and tail nodes.

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

class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.cache = {}
        self.head = Node()  # LRU (dummy)
        self.tail = Node()  # MRU (dummy)
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def _insert_mru(self, node):   # insert before tail
        prev = self.tail.prev
        prev.next = node
        node.prev = prev
        node.next = self.tail
        self.tail.prev = node

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

    def put(self, key, value):
        if key in self.cache: self._remove(self.cache[key])
        node = Node(key, value)
        self.cache[key] = node
        self._insert_mru(node)
        if len(self.cache) > self.cap:
            lru = self.head.next
            self._remove(lru)
            del self.cache[lru.key]
# All operations O(1)

Hard Merge K Sorted Lists

INSIGHT: Min-heap of size k. Always extract the minimum node across all k heads. Push the next node from that list. O(n log k).

import heapq

def mergeKLists(lists):
    heap = []
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))
    dummy = ListNode(0)
    curr = dummy
    while heap:
        val, i, node = heapq.heappop(heap)
        curr.next = node; curr = curr.next
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
    return dummy.next
# Time: O(n log k) | Space: O(k)

← Stack Trees →