链表 Linked List¶
Table of Contents¶
- 206. Reverse Linked List (Easy)
- 21. Merge Two Sorted Lists (Easy)
- 143. Reorder List (Medium)
- 19. Remove Nth Node From End of List (Medium)
- 141. Linked List Cycle (Easy)
- 23. Merge k Sorted Lists (Hard)
206. Reverse Linked List¶
from typing import Optional
from leetpattern.utils import LinkedList, ListNode
def reverse_list_iterative(head: Optional[ListNode]) -> Optional[ListNode]:
cur = head
prev = None
while cur:
temp = cur.next
cur.next = prev
prev = cur
cur = temp
return prev
def reverse_list_recursive(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)
def test_reverse_list():
ll = LinkedList([1, 2, 3, 4, 5])
ll.head = reverse_list_iterative(ll.head)
assert ll.to_array() == [5, 4, 3, 2, 1]
ll = LinkedList([1, 2, 3, 4, 5])
ll.head = reverse_list_recursive(ll.head)
assert ll.to_array() == [5, 4, 3, 2, 1]
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;
}
143. Reorder List¶
from typing import Optional
from leetpattern.utils import LinkedList, ListNode
# Linked List
def reorderList(head: Optional[ListNode]) -> None:
"""
Do not return anything, modify head in-place instead.
"""
if not head or not head.next:
return
# Middle of the linked list
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# Reverse the second half
pre, cur = None, slow
while cur:
temp = cur.next
cur.next = pre
pre = cur
cur = temp
# Merge two linked lists
first, second = head, pre
while second.next:
temp1, temp2 = first.next, second.next
first.next = second
second.next = temp1
first, second = temp1, temp2
def test_reorderList():
ll = LinkedList([1, 2, 3, 4, 5, 6])
assert ll.to_array() == [1, 2, 3, 4, 5, 6]
reorderList(ll.head)
assert ll.to_array() == [1, 6, 2, 5, 3, 4]
ll2 = LinkedList([1, 2, 3, 4, 5])
assert ll2.to_array() == [1, 2, 3, 4, 5]
reorderList(ll2.head)
assert ll2.to_array() == [1, 5, 2, 4, 3]
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]
141. Linked List Cycle¶
from typing import Optional
from leetpattern.utils import LinkedList, ListNode
def has_cycle(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
def test_has_cycle():
ll = LinkedList([3, 2, 0, -4])
ll.make_cycle(pos=1)
assert has_cycle(ll.head)
ll = LinkedList([1, 2])
ll.make_cycle(pos=0)
assert has_cycle(ll.head)
ll = LinkedList([1, 2, 3, 4, 5])
assert not has_cycle(ll.head)
#include <cassert>
#include <iostream>
#include "include/lists.hpp"
using namespace std;
class Solution {
public:
bool has_cycle(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 solution;
ListNode* head = LinkedList::build({3, 2, 0, -4});
// create cycle
head = LinkedList::make_cycle(head, 1);
assert(solution.has_cycle(head) == true);
// no cycle
ListNode* head2 = LinkedList::build({1, 2});
assert(solution.has_cycle(head2) == false);
// no cycle
ListNode* head3 = LinkedList::build({1});
assert(solution.has_cycle(head3) == false);
return 0;
}
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]