Linked List

1. Anatomy of a Node

A linked list consists of a sequence of nodes. Each node contains two pieces of information:

• Data: The actual value stored in the node (e.g., a number, a string).
• Next Pointer: A reference (or pointer) to the very next node in the sequence.

The entry point to the list is the first node, called the HEAD. The last node's "next" pointer points to NULL or None, signaling the end of the list.

2. Types of Linked Lists

Singly Linked List

This is the most basic type. Each node has a single pointer to the next node. Traversal is only possible in the forward direction.

  HEAD
   |
  [10] -> [20] -> [30] -> NULL

Doubly Linked List

Each node contains two pointers: a next pointer to the next node and a prev pointer to the previous node. This allows for traversal in both forward and backward directions, which can simplify some operations like deletion, at the cost of extra memory for the previous pointer.

  HEAD
   |
  NULL <- [10] <-> [20] <-> [30] -> NULL

Circular Linked List

A variation where the next pointer of the last node points back to the first node (the HEAD) instead of NULL, forming a circle. This can be useful for applications that need to cycle through a list repeatedly, like a carousel or a round-robin scheduler.

3. Arrays vs. Linked Lists

Choosing between an array and a linked list depends on the problem's requirements.

4. Core Techniques

Reversing a Linked List (Iterative)

This is a very common interview question. The key is to iterate through the list while keeping track of three pointers: previous, current, and next_node. In each step, you reverse the "next" pointer of the current node to point to previous, and then move all three pointers one step forward.

Initial:  prev=NULL, curr=[A], next=[B]
Step 1:   [A]->NULL, prev=[A], curr=[B], next=[C]
Step 2:   [B]->[A],  prev=[B], curr=[C], next=NULL
...and so on.

Fast & Slow Pointers

This powerful technique, also known as Floyd's Tortoise and the Hare algorithm, involves two pointers moving through the list at different speeds.

• Cycle Detection: Start both pointers at the head. Move the slow pointer by one step and the fast pointer by two steps. If there is a cycle, the fast pointer will eventually catch up to and equal the slow pointer.
• Finding the Middle: Move the slow pointer by one and the fast pointer by two. When the fast pointer reaches the end of the list, the slow pointer will be at the middle.

5. Classic Problems

Reverse Linked List

The canonical linked list problem. You should be comfortable with both iterative and recursive solutions.

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

Linked List Cycle

The standard application of the fast and slow pointer technique.

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

Merge Two Sorted Lists

A fundamental problem that tests pointer manipulation. It's a building block for merge sort on linked lists.

class Solution:
    def mergeTwoLists(self, 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 if list1 else list2
        
        return dummy.next

Remove Nth Node From End of List

A clever use of two pointers. Start a "fast" pointer and move it n steps ahead. Then start a "slow" pointer from the head. Move both pointers one step at a time until the fast pointer reaches the end. The slow pointer will now be at the node just before the one to be deleted.

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        left = dummy
        right = head
        
        for _ in range(n):
            right = right.next
            
        while right:
            left = left.next
            right = right.next
            
        # Delete the node
        left.next = left.next.next
        
        return dummy.next

LRU Cache

A famous hard-level design problem. To build a Least Recently Used (LRU) cache, you need a data structure that can provide O(1) insertion, deletion, and lookup. This is achieved by combining a Hash Map (for O(1) lookups) with a Doubly Linked List (for O(1) additions/removals of the most/least recently used items).

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

class LRUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.cache = {} # map key to node
        
        self.left, self.right = Node(0, 0), Node(0, 0)
        self.left.next, self.right.prev = self.right, self.left

    def remove(self, node):
        prev, nxt = node.prev, node.next
        prev.next, nxt.prev = nxt, prev

    def insert(self, node):
        prev, nxt = self.right.prev, self.right
        prev.next = nxt.prev = node
        node.next, node.prev = nxt, prev

    def get(self, key: int) -> int:
        if key in self.cache:
            self.remove(self.cache[key])
            self.insert(self.cache[key])
            return self.cache[key].val
        return -1

    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]