Linked List

A linked list is a fundamental data structure in computer science. It mainly allows efficient insertion and deletion operations compared to Arrays. Like arrays, it is also used to implement other data structures like stack, queue and deque.

Steps to Solve

Most of these questions follow the same framework

1. Identify pattern
   1. Reverse
   2. Merge
   3. Remove nth node
   4. Partition list
   5. Rotate list
   6. Reorder list
2. What pointer(s) do I update at each step
3. What pointers do I need to track
4. Use dummy node?
5. Edge cases?

Removing a Node From a Linked List

def remove_node(node):
	prev = node.prev
	nxt = node.next
	prev.next = nxt
	nxt.prev = prev
	# This just basically skips over our current node

Reversing a Linked List

def reverseList(head):
	if not head or head.next is None:
		return head
	revHead = reverseList(head.next)
	head.next.next = head # Making the current head the last node
	head.next = None # We are the last node so now point to nothing
	return revHead

curr = head
prev = None
while curr:
	nxt = curr.next
	curr.next = prev
	prev = curr
	curr = next
return prev

Cycles

• Leetcode - Linked List Cycle