Day 18: Linked List Interview Deep Dive 🐍

1. Core Concepts of Linked Lists

Think of a linked list as a treasure hunt. The `head` is your first clue. Each clue (a `Node`) tells you a piece of information (`data`) and, critically, where to find the next clue (`next` pointer). The hunt ends when you find a clue that points nowhere (`None`).

2. Array vs. Linked List: The Big Trade-Off

This is a classic interview question. The "right" choice depends entirely on the problem's requirements.

Feature Array / Dynamic Array (e.g., Python List) Linked List
Access (by index) ⚡️ Fast: $O(1)$ 🐌 Slow: $O(n)$
Insertion / Deletion (Start) 🐌 Slow: $O(n)$ (all elements must be shifted) ⚡️ Fast: $O(1)$
Insertion / Deletion (End) ⚡️ Fast: $O(1)$ (amortized for dynamic arrays) ⚡️ Fast: $O(1)$ (if a `tail` pointer is maintained)
Insertion / Deletion (Middle) 🐌 Slow: $O(n)$ 🐌 Slow: $O(n)$ (to find the element), but the pointer update is $O(1)$.
Memory Layout Contiguous (elements are neighbors in memory) Non-contiguous (nodes can be anywhere)
Cache Locality ✅ High (CPU caches can pre-fetch nearby elements) ❌ Low (nodes can be scattered, causing cache misses)
Best Use Case Frequent indexing/access is needed. Data size is known or stable. Frequent insertions/deletions at ends. Dynamic size is crucial.

3. Python Implementations & Operations

Singly Linked List Node

# The fundamental building block
class Node:
    def __init__(self, data):
        self.data = data  # Stores the value of the node
        self.next = None  # Pointer to the next node in the list

Doubly Linked List Node

# The node for a list you can traverse forwards and backwards
class DoublyNode:
    def __init__(self, data):
        self.data = data
        self.next = None  # Pointer to the next node
        self.prev = None  # Pointer to the previous node
Dummy Head / Sentinel Node: In interviews, using a `dummy` node (a placeholder node before the actual head) can simplify your code significantly. It eliminates edge cases for operations on the head of the list (e.g., insertion or deletion), as the head is now treated like any other node.

Example: Deleting a Node (Singly Linked List)

# In a SinglyLinkedList class
def delete_node(self, key):
    current = self.head
    
    # Case 1: The node to be deleted is the head
    if current and current.data == key:
        self.head = current.next
        current = None # Free memory
        print(f"Deleted head node with key {key}")
        return

    # Case 2: Search for the key, keeping track of the previous node
    prev = None
    while current and current.data != key:
        prev = current
        current = current.next

    # If the key was not found in the list
    if not current:
        print(f"Key {key} not found in the list.")
        return

    # Case 3: Unlink the node from the list
    prev.next = current.next
    current = None # Free memory
    print(f"Deleted node with key {key}")
    
# Time Complexity: O(n) - because we might have to search the whole list.
# Space Complexity: O(1) - we only use a few pointers.

4. Must-Know Interview Problems & Solutions

1. Reverse a Linked List

The goal is to reverse the direction of all pointers.

# Iterative Approach - O(n) Time, O(1) Space
def reverse_iterative(self):
    prev = None
    current = self.head
    while current:
        next_node = current.next  # Store the next node
        current.next = prev       # Reverse the current node's pointer
        prev = current            # Move prev one step forward
        current = next_node       # Move current one step forward
    self.head = prev              # The new head is the old tail

# Recursive Approach - O(n) Time, O(n) Space (due to recursion stack)
def reverse_recursive(self, current, prev=None):
    # Base case: if we are at the end of the list
    if not current:
        self.head = prev
        return
    
    next_node = current.next
    current.next = prev
    self.reverse_recursive(next_node, current)

2. Detect a Cycle (Floyd's Tortoise and Hare)

A classic problem solved elegantly with two pointers.

def has_cycle(self):
    slow = self.head
    fast = self.head

    while fast and fast.next:
        slow = slow.next          # Moves 1 step
        fast = fast.next.next     # Moves 2 steps
        
        if slow == fast:
            return True  # Pointers met, a cycle exists
    
    return False # Fast pointer reached the end, no cycle
Follow-up Question: Find the starting node of the cycle.
1. After detecting the cycle, reset one pointer (e.g., `slow`) to the `head`.
2. Move both `slow` and `fast` pointers one step at a time.
3. The node where they meet again is the start of the cycle.

3. Find the Nth Node from the End

Another two-pointer trick. Maintain a gap of 'N' nodes between them.

def find_nth_from_end(self, n):
    p1 = self.head # Fast pointer
    p2 = self.head # Slow pointer

    # Move p1 n steps into the list
    for _ in range(n):
        if not p1:
            return None # List is shorter than n
        p1 = p1.next

    # Move both pointers until p1 reaches the end
    while p1:
        p1 = p1.next
        p2 = p2.next
    
    return p2 # p2 is now at the Nth node from the end

4. Merge Two Sorted Linked Lists

Combine two sorted lists into a single sorted list.

# Iterative Approach with a dummy head
def merge_sorted_lists(l1, l2):
    dummy = Node(0)
    tail = dummy

    while l1 and l2:
        if l1.data < l2.data:
            tail.next = l1
            l1 = l1.next
        else:
            tail.next = l2
            l2 = l2.next
        tail = tail.next

    # Append the remaining nodes from either list
    if l1:
        tail.next = l1
    elif l2:
        tail.next = l2

    return dummy.next # The merged list starts after the dummy node

5. Real-World Use Cases & Advanced Concepts

6. Interview Cheat Sheet 🚀