Linked List¶
Table of Contents¶
- 160. Intersection of Two Linked Lists (Easy)
- 206. Reverse Linked List (Easy)
- 234. Palindrome Linked List (Easy)
- 141. Linked List Cycle (Easy)
- 142. Linked List Cycle II (Medium)
- 21. Merge Two Sorted Lists (Easy)
- 2. Add Two Numbers (Medium)
- 19. Remove Nth Node From End of List (Medium)
- 24. Swap Nodes in Pairs (Medium)
- 25. Reverse Nodes in k-Group (Hard)
- 138. Copy List with Random Pointer (Medium)
- 148. Sort List (Medium)
- 23. Merge k Sorted Lists (Hard)
- 146. LRU Cache (Medium)
160. Intersection of Two Linked Lists¶
"""
- Find the node at which the intersection of two singly linked lists begins.
"""
from typing import Optional
from leetpattern.utils import ListNode
# Hash Set
def getIntersectionNodeHash(
headA: ListNode, headB: ListNode
) -> Optional[ListNode]:
if not headA or not headB:
return None
visited = set()
cur = headA
while cur:
visited.add(cur)
cur = cur.next
cur = headB
while cur:
if cur in visited:
return cur
cur = cur.next
return None
# Two Pointers
def getIntersectionNodeTP(
headA: ListNode, headB: ListNode
) -> Optional[ListNode]:
if not headA or not headB:
return None
a, b = headA, headB
while a != b:
a = a.next if a else headB
b = b.next if b else headA
return a
listA = [4, 1, 8, 4, 5]
listB = [5, 6, 1, 8, 4, 5]
headA = list_from_array(listA)
print(headA)
# 4 -> 1 -> 8 -> 4 -> 5
headB = list_from_array(listB)
print(headB)
# 5 -> 6 -> 1 -> 8 -> 4 -> 5
headA.intersect(headB, 8)
print(getIntersectionNodeHash(headA, headB))
# 8 -> 4 -> 5
print(getIntersectionNodeTP(headA, headB))
# 8 -> 4 -> 5
206. Reverse Linked List¶
"""
- Reverse a singly linked list.
"""
from typing import Optional
from leetpattern.utils import ListNode
# Iterative
def reverseListIterative(head: Optional[ListNode]) -> Optional[ListNode]:
cur = head
prev = None
while cur:
temp = cur.next
cur.next = prev
prev = cur
cur = temp
return prev
# Recursive
def reverseListRecursive(head: Optional[ListNode]) -> Optional[ListNode]:
def reverse(cur, prev):
if not cur:
return prev
temp = cur.next
cur.next = prev
return reverse(temp, cur)
return reverse(head, None)
nums = [1, 2, 3, 4, 5]
head1 = list_from_array(nums)
print(head1)
# 1 -> 2 -> 3 -> 4 -> 5
print(reverseListIterative(head1))
# 5 -> 4 -> 3 -> 2 -> 1
head2 = list_from_array(nums)
print(reverseListRecursive(head2))
# 5 -> 4 -> 3 -> 2 -> 1
234. Palindrome Linked List¶
from typing import Optional
from leetpattern.utils import ListNode
# Linked List
def isPalindrome(head: Optional[ListNode]) -> bool:
if not head or not head.next:
return True
def middle(node):
fast, slow = node, node
while fast and fast.next:
fast = fast.next.next
slow = slow.next
return slow
def reverse(node):
cur, pre = node, None
while cur:
nxt = cur.next
cur.next = pre
pre = cur
cur = nxt
return pre
mid1 = head
mid2 = reverse(middle(head))
while mid2:
if mid1.val != mid2.val:
return False
mid1 = mid1.next
mid2 = mid2.next
return True
head = ListNode().create([1, 2, 2, 1])
print(isPalindrome(head)) # True
141. Linked List Cycle¶
"""
- Determine if a linked list has a cycle in it.
"""
from typing import Optional
from leetpattern.utils import ListNode
def hasCycle(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
print(hasCycle(list_from_array([3, 2, 0, -4]))) # False
print(hasCycle(list_from_array([3, 2, 0, -4], 1))) # True
#include <cassert>
#include <iostream>
using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
bool hasCycle(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (fast == slow) return true;
}
return false;
}
};
int main() {
Solution sol;
ListNode* head = new ListNode(3);
head->next = new ListNode(2);
head->next->next = new ListNode(0);
head->next->next->next = new ListNode(-4);
head->next->next->next->next = head->next; // Create a cycle
assert(sol.hasCycle(head) == true);
ListNode* head2 = new ListNode(1);
head2->next = new ListNode(2);
assert(sol.hasCycle(head2) == false);
ListNode* head3 = new ListNode(1);
assert(sol.hasCycle(head3) == false);
return 0;
}
142. Linked List Cycle II¶
"""
- Given a linked list, return the node where the cycle begins. If there is no cycle, return `None`.
"""
from typing import Optional
from leetpattern.utils import ListNode
def detectCycle(head: Optional[ListNode]) -> Optional[ListNode]:
slow, fast = head, head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
if slow == fast:
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow
return None
head1 = list_from_array([3, 2, 0, -4], 1)
print(detectCycle(head1).val) # 2
head2 = list_from_array([3, 2, 0, -4])
print(detectCycle(head2)) # None
#include <cassert>
#include <iostream>
using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode* detectCycle(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (fast == slow) {
slow = head;
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}
return slow;
}
}
return nullptr;
}
};
int main() {
Solution sol;
ListNode* head = new ListNode(3);
head->next = new ListNode(2);
head->next->next = new ListNode(0);
head->next->next->next = new ListNode(-4);
head->next->next->next->next = head->next; // Create a cycle
assert(sol.detectCycle(head) == head->next);
ListNode* head2 = new ListNode(1);
head2->next = new ListNode(2);
head2->next->next = head2; // Create a cycle
assert(sol.detectCycle(head2) == head2);
ListNode* head3 = new ListNode(1);
assert(sol.detectCycle(head3) == nullptr);
ListNode* head4 = nullptr;
assert(sol.detectCycle(head4) == nullptr);
return 0;
}
21. Merge Two Sorted Lists¶
"""
- Task: Merge the two linked lists into one sorted list.
"""
from typing import Optional
from leetpattern.utils import ListNode
# Linked List
def merge_two_lists(
list1: Optional[ListNode], list2: Optional[ListNode]
) -> Optional[ListNode]:
dummy = ListNode()
cur = dummy
while list1 and list2:
if list1.val < list2.val:
cur.next = list1
list1 = list1.next
else:
cur.next = list2
list2 = list2.next
cur = cur.next
if list1:
cur.next = list1
elif list2:
cur.next = list2
return dummy.next
#include <cassert>
#include <iostream>
#include <vector>
using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode* next) : val(x), next(next) {}
};
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode dummy;
ListNode* cur = &dummy;
while (list1 && list2) {
if (list1->val < list2->val) {
cur->next = list1;
list1 = list1->next;
} else {
cur->next = list2;
list2 = list2->next;
}
cur = cur->next;
}
cur->next = list1 ? list1 : list2;
return dummy.next;
}
};
int main() {
Solution sol;
ListNode* list1 = new ListNode(1, new ListNode(2, new ListNode(4)));
ListNode* list2 = new ListNode(1, new ListNode(3, new ListNode(4)));
ListNode* merged = sol.mergeTwoLists(list1, list2);
vector<int> res;
while (merged) {
res.push_back(merged->val);
merged = merged->next;
}
assert(res == std::vector<int>({1, 1, 2, 3, 4, 4}));
return 0;
}
2. Add Two Numbers¶
"""
- Represent the sum of two numbers as a linked list.
"""
from typing import Optional
from leetpattern.utils import ListNode, list_from_array, list_to_array
# Linked List
def add_two_numbers(
l1: Optional[ListNode], l2: Optional[ListNode]
) -> Optional[ListNode]:
dummy = ListNode()
cur = dummy
carry = 0
while l1 or l2:
v1 = l1.val if l1 else 0
v2 = l2.val if l2 else 0
carry, val = divmod(v1 + v2 + carry, 10)
cur.next = ListNode(val)
cur = cur.next
if l1:
l1 = l1.next
if l2:
l2 = l2.next
if carry:
cur.next = ListNode(val=carry)
return dummy.next
def test_add_two_numbers():
l1 = list_from_array([2, 4, 3])
l2 = list_from_array([5, 6, 4])
result = add_two_numbers(l1, l2)
assert list_to_array(result) == [7, 0, 8]
#include <cassert>
#include <vector>
using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode* next) : val(x), next(next) {}
};
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode dummy;
ListNode* cur = &dummy;
int carry = 0;
while (l1 || l2 || carry) {
if (l1) {
carry += l1->val;
l1 = l1->next;
}
if (l2) {
carry += l2->val;
l2 = l2->next;
}
cur->next = new ListNode(carry % 10);
cur = cur->next;
carry /= 10;
}
return dummy.next;
}
};
int main() {
Solution sol;
ListNode* l1 = new ListNode(2, new ListNode(4, new ListNode(3)));
ListNode* l2 = new ListNode(5, new ListNode(6, new ListNode(4)));
ListNode* result = sol.addTwoNumbers(l1, l2);
vector<int> expected = {7, 0, 8};
for (int val : expected) {
assert(result != nullptr && result->val == val);
result = result->next;
}
assert(result == nullptr); // End of list
return 0;
}
19. Remove Nth Node From End of List¶
"""
- Given the `head` of a linked list, remove the `n-th` node from the end of the list and return its head.
"""
from typing import Optional
from leetpattern.utils import ListNode, list_from_array, list_to_array
# Linked List
def removeNthFromEnd(head: Optional[ListNode], n: int) -> Optional[ListNode]:
dummy = ListNode(0, head)
fast, slow = dummy, dummy
for _ in range(n):
fast = fast.next
while fast.next:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return dummy.next
def test_removeNthFromEnd() -> None:
head = list_from_array([1, 2, 3, 4, 5])
assert (list_to_array(removeNthFromEnd(head, 2))) == [1, 2, 3, 5]
24. Swap Nodes in Pairs¶
"""
- Given a linked list, swap every two adjacent nodes and return its head.
"""
from typing import Optional
from leetpattern.utils import ListNode, list_from_array, list_to_array
def swap_pairs(head: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode(0, head)
n0 = dummy
n1 = dummy.next
while n1 and n1.next:
n2 = n1.next
n3 = n2.next
n0.next = n2
n2.next = n1
n1.next = n3
n0 = n1
n1 = n3
return dummy.next
def test_swap_pairs():
head = list_from_array([1, 2, 3, 4, 5])
assert list_to_array(swap_pairs(head)) == [2, 1, 4, 3, 5]
25. Reverse Nodes in k-Group¶
from typing import Optional
from leetpattern.utils import ListNode, list_from_array, list_to_array
# Linked List
def reverse_k_group(head: Optional[ListNode], k: int) -> Optional[ListNode]:
n = 0
cur = head
while cur:
n += 1
cur = cur.next
p0 = dummy = ListNode(next=head)
pre = None
cur = head
while n >= k:
n -= k
for _ in range(k):
nxt = cur.next
cur.next = pre
pre = cur
cur = nxt
nxt = p0.next
nxt.next = cur
p0.next = pre
p0 = nxt
return dummy.next
def test_reverse_k_group():
head = list_from_array([1, 2, 3, 4, 5])
assert list_to_array(reverse_k_group(head, 2)) == [2, 1, 4, 3, 5]
138. Copy List with Random Pointer¶
from typing import Optional
class Node:
def __init__(self, x: int, next: "Node" = None, random: "Node" = None):
self.val = int(x)
self.next = next
self.random = random
def copyRandomList(head: "Optional[Node]") -> "Optional[Node]":
if not head:
return None
# Copy nodes and link them together
cur = head
while cur:
new_node = Node(cur.val)
new_node.next = cur.next
cur.next = new_node
cur = new_node.next
# Copy random pointers
cur = head
while cur:
cur.next.random = cur.random.next if cur.random else None
cur = cur.next.next
# Separate the original and copied lists
cur = head
new_head = head.next
while cur:
new_node = cur.next
cur.next = new_node.next
new_node.next = new_node.next.next if new_node.next else None
cur = cur.next
return new_head
148. Sort List¶
from typing import Optional
from leetpattern.utils import ListNode, list_from_array
# Linked List
def sortListSort(head: Optional[ListNode]) -> Optional[ListNode]:
nums = []
while head:
nums.append(head.val)
head = head.next
dummy = ListNode()
cur = dummy
nums.sort()
for num in nums:
cur.next = ListNode(val=num)
cur = cur.next
return dummy.next
# Linked List
def sortListDivideConquer(head: Optional[ListNode]) -> Optional[ListNode]:
def middle(node):
fast, slow = node, node
while fast and fast.next:
pre = slow
slow = slow.next
fast = fast.next.next
pre.next = None
return slow
def merge_two_lists(l1, l2):
dummy = ListNode()
cur = dummy
while l1 and l2:
if l1.val < l2.val:
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
cur = cur.next
cur.next = l1 if l1 else l2
return dummy.next
if not head or not head.next:
return head
head2 = middle(head)
head = sortListDivideConquer(head)
head2 = sortListDivideConquer(head2)
return merge_two_lists(head, head2)
head = list_from_array([4, 2, 1, 3])
print(head) # 4 -> 2 -> 1 -> 3
print(sortListSort(head)) # 1 -> 2 -> 3 -> 4
print(sortListDivideConquer(head)) # 1 -> 2 -> 3 -> 4
23. Merge k Sorted Lists¶
"""
- Prerequisite: 21. Merge Two Sorted Lists
- Video explanation: [23. Merge K Sorted Lists - NeetCode](https://youtu.be/q5a5OiGbT6Q?si=SQ2dCvsYQ3LQctPh)
"""
import copy
import heapq
from typing import List, Optional
from leetpattern.utils import ListNode, list_from_array, list_to_array
def merge_k_lists_divide_conquer(
lists: List[Optional[ListNode]],
) -> Optional[ListNode]:
if not lists or len(lists) == 0:
return None
def mergeTwo(l1, l2):
dummy = ListNode()
cur = dummy
while l1 and l2:
if l1.val < l2.val:
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
cur = cur.next
cur.next = l1 if l1 else l2
return dummy.next
while len(lists) > 1:
merged = []
for i in range(0, len(lists), 2):
l1 = lists[i]
l2 = lists[i + 1] if i + 1 < len(lists) else None
merged.append(mergeTwo(l1, l2))
lists = merged
return lists[0]
def merge_k_lists_heap(lists: List[Optional[ListNode]]) -> Optional[ListNode]:
dummy = ListNode()
cur = dummy
min_heap = [] # (val, idx, node)
for idx, head in enumerate(lists):
if head:
heapq.heappush(min_heap, (head.val, idx, head))
while min_heap:
_, idx, node = heapq.heappop(min_heap)
cur.next = node
cur = cur.next
node = node.next
if node:
heapq.heappush(min_heap, (node.val, idx, node))
return dummy.next
def test_merge_k_lists() -> None:
n1 = list_from_array([1, 4])
n2 = list_from_array([1, 3])
n3 = list_from_array([2, 6])
lists = [n1, n2, n3]
lists1 = copy.deepcopy(lists)
lists2 = copy.deepcopy(lists)
assert (list_to_array(merge_k_lists_divide_conquer(lists1))) == [
1,
1,
2,
3,
4,
6,
]
assert (list_to_array(merge_k_lists_heap(lists2))) == [1, 1, 2, 3, 4, 6]
146. LRU Cache¶
"""
- Design and implement a data structure for **Least Recently Used (LRU) cache**. It should support the following operations: get and put.
- [lru](https://media.geeksforgeeks.org/wp-content/uploads/20240909142802/Working-of-LRU-Cache-copy-2.webp)
- 
| Data structure | Description |
| ------------------ | ----------------------------- |
| Doubly Linked List | To store the key-value pairs. |
| Hash Map | To store the key-node pairs. |
"""
from collections import OrderedDict
# Doubly Linked List
class Node:
def __init__(self, key=0, val=0):
self.key = key
self.val = val
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity: int):
self.cap = capacity
self.cache = {}
self.head = Node()
self.tail = Node()
self.head.next = self.tail
self.tail.prev = self.head
def remove(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def add_to_last(self, node):
self.tail.prev.next = node
node.prev = self.tail.prev
node.next = self.tail
self.tail.prev = node
def move_to_last(self, node):
self.remove(node)
self.add_to_last(node)
def get(self, key: int) -> int:
if key not in self.cache:
return -1
node = self.cache[key]
self.move_to_last(node)
return node.val
def put(self, key: int, value: int) -> None:
if key in self.cache:
node = self.cache[key]
node.val = value
self.move_to_last(node)
return None
if len(self.cache) == self.cap:
del self.cache[self.head.next.key]
self.remove(self.head.next)
node = Node(key=key, val=value)
self.cache[key] = node
self.add_to_last(node)
# OrderedDict
class LRUCacheOrderedDict:
def __init__(self, capacity: int):
self.cache = OrderedDict()
self.cap = capacity
def get(self, key: int):
if key not in self.cache:
return -1
self.cache.move_to_end(key, last=True)
return self.cache[key]
def put(self, key: int, value: int):
if key in self.cache:
self.cache.move_to_end(key, last=True)
elif len(self.cache) >= self.cap:
self.cache.popitem(last=False)
self.cache[key] = value
cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
assert cache.get(1) == 1
cache.put(3, 3)
assert cache.get(2) == -1
cache.put(4, 4)
assert cache.get(1) == -1
assert cache.get(3) == 3
assert cache.get(4) == 4
cache = LRUCacheOrderedDict(2)
cache.put(1, 1)
cache.put(2, 2)
assert cache.get(1) == 1
cache.put(3, 3)
assert cache.get(2) == -1
cache.put(4, 4)
assert cache.get(1) == -1
assert cache.get(3) == 3
assert cache.get(4) == 4
print("LRU Cache passed")
print("LRU Cache Ordered Dict passed")
#include <cassert>
#include <iostream>
#include <unordered_map>
using namespace std;
class Node {
public:
int key;
int val;
Node *prev;
Node *next;
Node(int k = 0, int v = 0) : key(k), val(v), prev(nullptr), next(nullptr) {}
};
class LRUCache {
private:
int cap;
unordered_map<int, Node *> cache;
Node *head;
Node *tail;
void remove(Node *node) {
node->prev->next = node->next;
node->next->prev = node->prev;
}
void insert_to_last(Node *node) {
tail->prev->next = node;
node->prev = tail->prev;
tail->prev = node;
node->next = tail;
}
void move_to_last(Node *node) {
remove(node);
insert_to_last(node);
}
public:
LRUCache(int capacity) {
this->cap = capacity;
head = new Node();
tail = new Node();
head->next = tail;
tail->prev = head;
}
int get(int key) {
if (cache.find(key) != cache.end()) {
Node *node = cache[key];
move_to_last(node);
return node->val;
}
return -1;
}
void put(int key, int value) {
if (cache.find(key) != cache.end()) {
Node *node = cache[key];
node->val = value;
move_to_last(node);
} else {
Node *newNode = new Node(key, value);
cache[key] = newNode;
insert_to_last(newNode);
if ((int)cache.size() > cap) {
Node *removed = head->next;
remove(removed);
cache.erase(removed->key);
delete removed;
}
}
}
};
int main() {
LRUCache lru(2);
lru.put(1, 1);
lru.put(2, 2);
assert(lru.get(1) == 1); // returns 1
lru.put(3, 3); // evicts key 2
assert(lru.get(2) == -1); // returns -1 (not found)
lru.put(4, 4); // evicts key 1
assert(lru.get(1) == -1); // returns -1 (not found)
assert(lru.get(3) == 3); // returns 3
assert(lru.get(4) == 4); // returns 4
return 0;
}