- Understand doubly linked lists for O(1) deletion with node pointer
- See LRU cache implementation combining hash map and doubly linked list
- Learn palindrome check and list reordering with slow/fast pointers
Advanced Linked List Concepts
Basic operations cover most needs. Now let's tackle advanced patterns and problems.
Doubly Linked Lists
Each node has prev and next pointers.
class DoublyNode:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
null ← [A] ↔ [B] ↔ [C] → null
Advantages:
- Traverse both directions
- Delete a node in O(1) if you have pointer to it (no need to find predecessor)
- Easier to implement certain operations
Disadvantage: Extra memory for prev pointers.
Insert after a node:
def insertAfter(node, data):
new_node = DoublyNode(data)
new_node.next = node.next
new_node.prev = node
if node.next is not None:
node.next.prev = new_node
node.next = new_node
Delete a node (given pointer to it):
def deleteNode(node):
if node.prev is not None:
node.prev.next = node.next
if node.next is not None:
node.next.prev = node.prev
O(1). No traversal needed.
Circular Linked Lists
Last node points back to first instead of null.
[A] → [B] → [C] → (back to A)
Use case: Round-robin scheduling, circular buffers, multiplayer turn-based games.
Traverse (be careful not to loop forever):
def traverse(head):
if head is None:
return
current = head
while True:
print(current.data)
current = current.next
if current == head:
break
Insert at end:
def insertAtEnd(head, data):
new_node = Node(data)
if head is None:
new_node.next = new_node # Points to itself
return new_node
current = head
while current.next != head:
current = current.next
current.next = new_node
new_node.next = head
return head
Skip Lists
Linked list with multiple levels of pointers for faster search.
Level 2: A ---------> C ---------> E
Level 1: A ----> B -> C ----> D -> E
Level 0: A -> B -> C -> D -> E
Search starts at highest level, skips nodes, drops down when needed. Average O(log n) search instead of O(n).
Think of it as a linked list with "express lanes." Complex to implement, rarely used (balanced trees are more common), but elegant.
Intersection of Two Lists
Find the node where two linked lists intersect.
List 1: A → B → C ↘
E → F → G
List 2: D -----→ /
Both lists share E → F → G.
Approach: Find lengths, advance longer list by difference, then move both together until they meet.
def getIntersection(head1, head2):
len1 = getLength(head1)
len2 = getLength(head2)
# Advance longer list
diff = abs(len1 - len2)
if len1 > len2:
for _ in range(diff):
head1 = head1.next
else:
for _ in range(diff):
head2 = head2.next
# Move together
while head1 is not None and head2 is not None:
if head1 == head2:
return head1 # Intersection node
head1 = head1.next
head2 = head2.next
return None # No intersection
O(n + m).
Palindrome Check
Check if a linked list is a palindrome (same forwards and backwards).
Approach:
- Find middle (slow/fast)
- Reverse second half
- Compare first half and reversed second half
def isPalindrome(head):
if head is None or head.next is None:
return True
# Find middle
slow = fast = head
while fast.next is not None and fast.next.next is not None:
slow = slow.next
fast = fast.next.next
# Reverse second half
second_half = reverse(slow.next)
# Compare
first = head
second = second_half
is_palin = True
while second is not None:
if first.data != second.data:
is_palin = False
break
first = first.next
second = second.next
# Optional: restore list by reversing second half again
slow.next = reverse(second_half)
return is_palin
O(n) time, O(1) space.
Flatten a Multilevel List
Linked list nodes have a child pointer in addition to next.
1 → 2 → 3 → 4
↓
5 → 6
↓
7 → 8
Flatten to: 1 → 2 → 5 → 7 → 8 → 6 → 3 → 4
Use a stack or recursion to traverse depth-first.
def flatten(head):
if head is None:
return None
stack = [head]
prev = None
while stack:
current = stack.pop()
if prev is not None:
prev.next = current
current.prev = prev
if current.next is not None:
stack.append(current.next)
if current.child is not None:
stack.append(current.child)
current.child = None
prev = current
return head
O(n) where n is total nodes.
LRU Cache with Linked List
Least Recently Used cache: evict least recently used item when full.
Use doubly linked list + hash map:
- Hash map: key → node (O(1) access)
- Doubly linked list: maintain usage order (most recent at head)
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.cache = {} # key → node
self.head = DoublyNode(0, 0) # Dummy head
self.tail = DoublyNode(0, 0) # Dummy tail
self.head.next = self.tail
self.tail.prev = self.head
def get(self, key):
if key not in self.cache:
return -1
node = self.cache[key]
self._remove(node)
self._add_to_head(node)
return node.value
def put(self, key, value):
if key in self.cache:
self._remove(self.cache[key])
node = DoublyNode(key, value)
self.cache[key] = node
self._add_to_head(node)
if len(self.cache) > self.capacity:
lru = self.tail.prev
self._remove(lru)
del self.cache[lru.key]
def _remove(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def _add_to_head(self, node):
node.next = self.head.next
node.prev = self.head
self.head.next.prev = node
self.head.next = node
O(1) for get and put. Hash map gives instant access, doubly linked list gives O(1) add/remove.
Sorting a Linked List
Merge sort works well for linked lists.
def mergeSort(head):
if head is None or head.next is None:
return head
# Find middle
slow = fast = head
prev = None
while fast is not None and fast.next is not None:
prev = slow
slow = slow.next
fast = fast.next.next
# Split
prev.next = None
# Sort halves
left = mergeSort(head)
right = mergeSort(slow)
# Merge
return mergeSorted(left, right)
O(n log n) time, O(log n) space for recursion stack.
Quicksort is harder for linked lists (no random access for pivot selection).
Reorder List
Given: L0 → L1 → L2 → ... → Ln-1 → Ln
Reorder to: L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → ...
Example: 1 → 2 → 3 → 4 → 5 becomes 1 → 5 → 2 → 4 → 3
Approach:
- Find middle
- Reverse second half
- Merge two halves alternately
def reorderList(head):
if head is None or head.next is None:
return
# Find middle
slow = fast = head
while fast.next is not None and fast.next.next is not None:
slow = slow.next
fast = fast.next.next
# Reverse second half
second = reverse(slow.next)
slow.next = None
# Merge alternately
first = head
while second is not None:
temp1 = first.next
temp2 = second.next
first.next = second
second.next = temp1
first = temp1
second = temp2
O(n).
XOR Linked List
Memory-efficient doubly linked list using XOR.
Each node stores prev XOR next instead of separate pointers.
# Conceptual (not directly implementable in Python due to pointer arithmetic)
class XORNode:
def __init__(self, data):
self.data = data
self.npx = 0 # XOR of prev and next addresses
To traverse: if you know prev, you can compute next via next = prev XOR npx.
Saves memory but harder to implement and debug. Rarely used in practice.
The Takeaway
Advanced linked list techniques:
- Doubly linked: O(1) delete with node pointer
- Circular: No end, useful for round-robin
- Skip lists: Multi-level for O(log n) search
- Two-pointer tricks: Intersection, palindrome, reordering
- Combine with hash maps: LRU cache in O(1)
Understanding these means recognizing:
- When extra pointers (prev, child) simplify problems
- How to use slow/fast pointers creatively
- When linked lists integrate with other structures (hash maps, stacks)
Master these, and you'll solve complex linked list problems efficiently.