Linked List

Problems

#	Problem	Difficulty	Hint	Tags
206	Reverse Linked List - LeetCode	Easy	Hint Keep two pointers for the current and previous nodes and move the current nodes next pointer to the previous node.	#linkedlist #recursion
21	Merge Two Sorted Lists - LeetCode	Easy	Hint Create a dummy node to create the list we will return. Compare the two nodes and put the lower value in the dummy list.	#linkedlist #recursion
141	Linked List Cycle - LeetCode	Easy	Hint Use two pointers, one fast and one slow with the fast moving twice as fast as the slow pointer. If they meet, there is a cycle.	#linkedlist #twopointers
143	Reorder List - LeetCode	Medium	Hint The list is split into two halves, the first half and the second half. We first split the two lists, reverse the second and then merge them.	#linkedlist #twopointers
19	Remove Nth Node From End of List - LeetCode	Medium	Hint Use a loop to move the right pointer to n nodes ahead of the head. Move pointers same speed and when the right reaches the end you are before the node you want to delete (use a dummy node pointing to head).	#linkedlist #twopointers
138	Copy List with Random Pointer - LeetCode	Medium	Hint Create a hash map storing copies of nodes in first pass. In second pass, assign the pointers using the map.	#linkedlist #hashtable
146	LRU Cache - LeetCode	Medium	Hint Use a Double Linked List with dummy nodes on either end. Move nodes to front when they are used, remove nodes from left when cache exceeds capacity. For the cache, use a dict with the keys pointing to nodes.	#hashtable #linkedlist #design #doublylinkedlist

Like Arrays, linked lists are a sequential collection of data. However, unlike Arrays, they are not represented by a physical block in memory but rather an address pointing to the next element. It is a collection of nodes which together form a list. In its most basic form, each node contains the data and an address pointing to the next node.

Types of linked lists

Singly

Basic linked list, each node points to its next one with the last pointer pointing to null.

Doubly

A linked list which has two pointers, one to its next node and one to its previous node.

Circular

A linked list which is circular in nature, in that the last node's next pointer points to the first node and the prev pointer of the first node points to the last node.

Common routines

Many problems use the following techniques:

Reversing a linked list
Counting the number of nodes
Finding the middle node of the linked list using two pointers (fast/slow)
Merging two linked lists together

Techniques

Using a dummy node

dummy = node = ListNode()

This creates a dummy node and a pointer node which is assigned to the same reference ListNode(). This allows us to keep reference to the start of the list while we continue to modify node.next since those changes will also be reflected in dummy since they both reference the same object.

Two pointers

Two Pointers are also common in linked list problems.

Detecting cycles - have two pointers where one pointer increments twice as fast as the other, if the two pointers meet, there is a cycle.
Getting the middle node - have two pointers where one pointer increments twice as fas as the other, when the faster one reaches the end, the slow pointer is at the middle node.
Getting kth from last node - have two pointers, one starting k nodes ahead of the other, when the node ahead reaches the end, the other node is k nodes behind.
- Use a dummy node here if you need the node before the kth node.