LeetCode刷题记录（链表篇）
LeetCode刷题记录（链表篇），个人向。
为了锻炼代码能力，会交替使用不同编程语言完成答案。
[203] Remove Linked List Elements
难度：Easy
语言：Rust
题目描述。
基本的数据结构操作，按道理没有难度可言。问题是如果用Rust来写，难度就会暴增。
pub fn remove_elements(head: Option<Box<ListNode>>, val: i32) -> Option<Box<ListNode>> {
let mut dummy_head = Box::new(ListNode::new(0));
dummy_head.next = head;
let mut cur = dummy_head.as_mut();
while let Some(nxt) = cur.next.as_mut() {
if nxt.val == val {
cur.next = nxt.next.take();
} else {
cur = cur.next.as_mut().unwrap();
}
}
dummy_head.next
}
[707] Design Linked List
难度：Medium
语言：C++
题目描述。
实现一个链表，可以是单向链表或双向链表。基本的数据结构实现，这居然是Medium？
虽然如此，还是需要注意一些细节，不能看错题目，例如addAtIndex是在指定节点之前而不是之后插入；以及当index等于length时需要在链表尾部插入。
本人这里实现的是双链表。相比题目要求实现的函数，额外增加实现了可复用函数get_node用来精简代码。实际上这里addAtHead和addAtTail函数还可以复用addAtIndex的代码，但是没有必要了，因为这两个函数本身就很简单，也不需要一些多余的条件判断，不复用可以提升一下性能。
此外，这里的实现还加了一个优化，即get_node的时候会判断一下目标是在链表前半段还是后半段，即从head遍历过去快还是从tail遍历过去快，充分榨干双向链表性能。
class MyLinkedList {
public:
struct Node {
int val;
Node* next;
Node* prev;
Node(int val) : val(val), next(nullptr), prev(nullptr) {}
};
Node* head;
Node* tail;
int length;
MyLinkedList() {
head = new Node(0);
tail = new Node(0);
length = 0;
head->next = tail;
tail->prev = head;
}
Node* get_node(int index) {
if (index < 0 || index >= length) {
return nullptr;
}
Node* curr = head->next;
if (index < length / 2) {
for (int i = 0; i < index; ++i) {
curr = curr->next;
}
} else {
// Opt: near to tail
curr = tail->prev;
for (int i = 0; i < length - index - 1; ++i) {
curr = curr->prev;
}
}
return curr;
}
int get(int index) {
Node* node = get_node(index);
return node != nullptr ? node->val : -1;
}
void addAtHead(int val) {
Node* node = new Node(val);
head->next->prev = node;
node->next = head->next;
node->prev = head;
head->next = node;
length++;
}
void addAtTail(int val) {
Node* node = new Node(val);
tail->prev->next = node;
node->prev = tail->prev;
node->next = tail;
tail->prev = node;
length++;
}
void addAtIndex(int index, int val) {
Node* node = new Node(val);
Node* curr = tail;
if (index != length) {
curr = get_node(index);
}
if (curr == nullptr) {
return;
}
node->prev = curr->prev;
curr->prev->next = node;
node->next = curr;
curr->prev = node;
length++;
}
void deleteAtIndex(int index) {
Node* curr = get_node(index);
if (curr == nullptr) {
return;
}
curr->prev->next = curr->next;
curr->next->prev = curr->prev;
delete curr;
length--;
}
};
[206] Reverse Linked List
难度：Easy
语言：Python
题目描述。
没有任何难度的极简题目，包含return一共只用八行代码。遍历链表，每次记录一下下一个节点（succ），然后翻转当前节点指针即可。
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
prev = None
curr = head
while curr is not None:
succ = curr.next
curr.next = prev
prev = curr
curr = succ
return prev
[24] Swap Nodes in Pairs
难度：Medium
语言：C++
题目描述。
题目不难，脑里想好每次循环时要做的操作即可。网上有解法是把每次操作分为三个步骤。本人的解法只把操作分为两个步骤，缺点是每次要检查一下curr->next是否存在，即元素个数是否是奇数个。
ListNode* swapPairs(ListNode* head) {
ListNode* dummy_head = new ListNode(0, head);
ListNode* prev = dummy_head;
ListNode* curr = head;
ListNode* next_pair = nullptr;
while (curr) {
if (!(curr->next)) {
prev->next = curr;
prev = curr;
break;
}
next_pair = curr->next->next;
curr->next->next = curr;
prev->next = curr->next;
prev = curr;
curr = next_pair;
}
prev->next = nullptr;
ListNode* result = dummy_head->next;
delete dummy_head;
return result;
}
[19] Remove Nth Node From End of List
难度：Medium
语言：Python
题目描述。
小学生都会的最直观的想法就是先扫一遍得出size再遍历第二遍找要删除的node，但是要扫描两遍，不够优雅。网上的解法是使用快慢指针，一前一后保持距离，就可以找到倒数第N个node。这种解法看似只用了一次遍历，但每次循环从一次操作变成了两次操作，本质其实是一样的，看起来花里胡哨了而已（毫无含金量的Medium）。但循环变量更新和条件判断本身也是有开销的，快慢指针这种解法把两个循环拍扁合成一个循环，也不能说没有提升吧。
真正的只需要一次Walk的解法应该是使用哈希表把node存起来，但是这需要O(n)的空间复杂度，性价比貌似不是很高。
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
dummy_head = ListNode(0, head)
fast = dummy_head
slow = dummy_head
for _ in range(0, n):
fast = fast.next
if fast is None:
# Actually this will not happen because 1 <= n <= sz
return None
fast = fast.next
while fast is not None:
slow = slow.next
fast = fast.next
slow.next = slow.next.next
return dummy_head.next
[160] Intersection of Two Linked Lists
难度：Easy
语言：C++
题目描述。
题目要求O(m+n)的时间复杂度和O(1)的空间复杂度，因此哈希表之类的把节点存下来的解法是不能用的。一种容易想到的做法是先算一下两个链表的长度，然后把链表尾部对齐，从短链表的头部开始依次对比两个链表对应位置的节点是否相同（说人话就是把长链表开头超出的部分截断）。
网上也有一种双指针的解法，用了一点数学技巧，说实话真的到了面试笔试临时很难想出来。对齐链表的方法虽然代码长了一些但思路很简单，个人还是更推荐。
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
int size_a = 0;
int size_b = 0;
int diff = 0;
ListNode *tmp_a = headA;
ListNode *tmp_b = headB;
while (tmp_a) {
tmp_a = tmp_a->next;
size_a++;
}
while (tmp_b) {
tmp_b = tmp_b->next;
size_b++;
}
tmp_a = headA;
tmp_b = headB;
diff = size_a - size_b;
while (diff > 0) {
tmp_a = tmp_a->next;
--diff;
}
while (diff < 0) {
tmp_b = tmp_b->next;
++diff;
}
while (tmp_a && tmp_b) {
if (tmp_a == tmp_b) {
return tmp_a;
}
tmp_a = tmp_a->next;
tmp_b = tmp_b->next;
}
return nullptr;
}
[142] Linked List Cycle II
难度：Medium
语言：Python
题目描述。
较有难度的一道题。
图论中，环是只有首末顶点重复的非空路径。直观想法是判断遍历中是否会第二次经过同一个点，但由于题目要求O(1)的空间复杂度，我们显然并不能用哈希表之类的数据结构把见过的点都存下来。因此这道题只能用一些数学推断来解，而难度也源于此。
数学推导的具体过程可以参考这篇解答。简单来说，关键在于通过以下两点
- 快指针走过的长度是慢指针的两倍
- 把快指针和慢指针走过的长度都用
x，y和z表示出来
来共同解出从头节点到环入口的距离x。由于通过第一次快慢指针的相遇，y和z都已经是已知值，所以我们就可以成功找出x，并且发现x原来就等于z再加上若干圈环的长度。最后，同时从头结点和相遇节点出发，找出x对应位置的节点即可。
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
slow = head
fast = head
while True:
if fast is None or fast.next is None:
return None
fast = fast.next.next
slow = slow.next # No need to check slow
if slow == fast:
break
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow
总结
涉及链表基本操作的题（如203、707、206和24）基本没有难度，要点就是加一个dummy_head可以大大减小代码的复杂程度（避免对头结点特殊情况的判断）。
涉及算法的题目则都会要求O(1)的空间复杂度，也就是我们不能把节点都存下来。在链表有限的遍历方式下，大多数题目都会使用双指针来解，通过推导以及利用多个指针之间的关系来达成我们想要的目的，例如
- [19] Remove Nth Node From End of List
两个指针间的距离保持固定，因此前一个指针就是倒数第N个节点。 - [160] Intersection of Two Linked Lists
两个指针从不同链表开始交错遍历，到相交节点走过的距离相同。 - [142] Linked List Cycle II
- 两个指针走过的距离有两倍的关系，可以列方程把
x用已知的y和z表示。 - 两个指针走过的距离相同，来找到
x对应的节点。
- 两个指针走过的距离有两倍的关系，可以列方程把
补充
[234] Palindrome Linked List
难度：Easy
语言：C++
题目描述。
难点在于的时间复杂度和的空间复杂度。
这里我们先使用快慢指针（快指针走两步，慢指针走一步）的方式找到链表中间位置（其实先遍历一遍得到链表长度再直接走到中间也是一样的）。然后我们翻转链表的后半部分，再同时遍历前半和后半部分看是否一样即可。
该算法过程修改了原链表。虽然不恢复链表也能通过测试，但我们还是通过slow->next = reverseList(reversedHead);的方式恢复了链表。
class Solution {
public:
bool isPalindrome(ListNode *head) {
ListNode *fast = head;
ListNode *slow = head;
bool result = true;
while (fast->next && fast->next->next) {
slow = slow->next;
fast = fast->next->next;
}
ListNode *reversedHead = reverseList(slow->next);
ListNode *p1 = head;
ListNode *p2 = reversedHead;
while (p2) {
if (p1->val != p2->val) {
result = false;
}
p1 = p1->next;
p2 = p2->next;
}
// Optional: recover the list
slow->next = reverseList(reversedHead);
return result;
}
ListNode *reverseList(ListNode *head) {
ListNode *cur = head;
ListNode *pre = nullptr;
while (cur) {
ListNode *succ = cur->next;
cur->next = pre;
pre = cur;
cur = succ;
}
return pre;
}
};
[141] Linked List Cycle
难度：Easy
语言：C++
题目描述。
相当于[142] Linked List Cycle II的前置题目。这里不需要找到环的入口，只需要判断是否存在环即可。我们使用快慢指针看是否能相遇即可。
class Solution {
public:
bool hasCycle(ListNode *head) {
ListNode *fast = head;
ListNode *slow = head;
while (fast && fast->next) {
fast = fast->next->next;
slow = slow->next;
if (fast == slow) {
return true;
}
}
return false;
}
};
[21] Merge Two Sorted Lists
难度：Easy
语言：C++
题目描述。
类似归并排序，每次选两个链表里面大的那个节点作为后继即可。
这里用dummy节点简化了头结点判断，又用了succ作为p1或p2的引用来减少重复代码。
class Solution {
public:
ListNode *mergeTwoLists(ListNode *list1, ListNode *list2) {
ListNode *p1 = list1;
ListNode *p2 = list2;
ListNode *dummy = new ListNode(0);
ListNode *cur = dummy;
while (p1 && p2) {
ListNode *&succ = p1->val < p2->val ? p1 : p2;
cur->next = succ;
cur = succ;
succ = succ->next;
}
cur->next = p1 ? p1 : p2;
ListNode *result = dummy->next;
delete dummy;
return result;
}
};
[2] Add Two Numbers
难度：Medium
语言：C++
题目描述。
链表已经倒序，那么就很方便，按位相加num1 + num2 + carry，得到下一位的数字sum % 10和carry = sum / 10。
class Solution {
public:
ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
ListNode *dummy = new ListNode(0);
ListNode *cur = dummy;
int carry = 0;
while (l1 || l2 || carry) {
int num1 = l1 ? l1->val : 0;
int num2 = l2 ? l2->val : 0;
int sum = num1 + num2 + carry;
cur->next = new ListNode(sum % 10);
carry = sum / 10;
if (l1) {
l1 = l1->next;
}
if (l2) {
l2 = l2->next;
}
cur = cur->next;
}
ListNode *result = dummy->next;
delete dummy;
return result;
}
};
[25] Reverse Nodes in k-Group
难度：Hard
语言：C++
题目描述。
每次找到当前组的开头curHead和下一组的开头nextHead，然后一组一组翻转即可。
问题在于，翻转后我们还需要把当前组重新与前后组连上。因此我们用pre记录上一组的结尾，翻转后手动把pre连上当前组翻转后的开头。我们又把nextHead传给翻转函数，使当前组的旧开头即新结尾连上nextHead。
class Solution {
public:
ListNode *reverseKGroup(ListNode *head, int k) {
ListNode *pre = nullptr;
ListNode *curHead = head;
ListNode *nextHead = curHead;
ListNode *newHead = head;
while (curHead) {
for (int i = 0; i < k; ++i) {
if (!nextHead) {
return newHead;
}
nextHead = nextHead->next;
}
(pre ? pre->next : newHead) = reverseOneList(curHead, nextHead);
pre = curHead; // curHead become tail now
curHead = nextHead;
}
return newHead;
}
ListNode *reverseOneList(ListNode *head, ListNode *end) {
ListNode *cur = head;
ListNode *pre = end;
while (cur != end) {
ListNode *succ = cur->next;
cur->next = pre;
pre = cur;
cur = succ;
}
return pre;
}
};
[138] Copy List with Random Pointer
难度：Medium
语言：C++
题目描述。
三次遍历。
- 第一次遍历把复制的节点插到原节点后面变成
A --> A' --> B --> B' --> C --> C'。 - 第二次遍历用来填
random。A'的random就是A的random的next。 - 第三次遍历用来把
A' --> B' --> C'拆出来。
class Solution {
public:
Node *copyRandomList(Node *head) {
if (!head) {
return nullptr;
}
// A --> A' --> B --> B' --> C --> C'
Node *cur = head;
while (cur) {
Node *nxt = cur->next;
cur->next = new Node(cur->val);
cur->next->next = nxt;
cur = nxt;
}
// Set random pointers for A', B' and C'
cur = head;
while (cur) {
cur->next->random = cur->random ? cur->random->next : nullptr;
cur = cur->next->next;
}
// Extract the new list
cur = head;
Node *newHead = head->next;
while (cur) {
Node *nxt = cur->next->next;
cur->next->next = nxt ? nxt->next : nullptr;
cur->next = nxt;
cur = nxt;
}
return newHead;
}
};
[148] Sort List
难度：Medium
语言：C++
题目描述。
较有难度的一道题。难度在于，为了同时达到的时间复杂度和的空间复杂度，我们考虑使用自底向上（迭代法）的归并排序。而这样的代码实现在链表上显然是比较复杂的，很容易出错。
class Solution {
public:
ListNode *sortList(ListNode *head) {
if (!head) {
return nullptr;
}
ListNode *dummy = new ListNode(0, head);
// Get the length of the list
ListNode *cur = head;
int length = 0;
while (cur) {
++length;
cur = cur->next;
}
// Merge Sort
for (int i = 1; i < length; i <<= 1) {
ListNode *pre = dummy;
cur = dummy->next;
while (cur) {
// 1. Get head1
ListNode *head1 = cur;
// 2. Get head2
for (int j = 1; j < i && cur->next; ++j) {
cur = cur->next;
}
// Now cur is the tail of list1.
// cur->next is head2.
ListNode *head2 = cur->next;
cur->next = nullptr;
cur = head2;
// 3. Get next cur
for (int j = 1; j < i && cur; ++j) {
cur = cur->next;
}
ListNode *nxt = nullptr;
if (cur) {
nxt = cur->next;
cur->next = nullptr;
}
// 4. Merge
pre->next = merge(head1, head2);
// 5. Set next pre and cur
while (pre->next) {
pre = pre->next;
}
cur = nxt;
}
}
ListNode *result = dummy->next;
delete dummy;
return result;
}
ListNode *merge(ListNode *head1, ListNode *head2) {
ListNode *dummy = new ListNode(0);
ListNode *pre = dummy;
while (head1 && head2) {
ListNode *&choosen = head1->val < head2->val ? head1 : head2;
pre->next = choosen;
pre = choosen;
choosen = choosen->next;
}
pre->next = head1 ? head1 : head2;
ListNode *head = dummy->next;
delete dummy;
return head;
}
};
[23] Merge k Sorted Lists
难度：Hard
语言：C++
题目描述。
相比[21] Merge Two Sorted Lists只是把两个链表扩展成了k个链表。
简单的想法是我们每次从k个链表里面取值最小的那个节点即可。这里则使用优先级队列进一步优化了这个从k个里面找最小节点的过程。
class Solution {
public:
ListNode *mergeKLists(vector<ListNode *> &lists) {
struct test {
bool operator()(const ListNode *a, const ListNode *b) {
return a->val > b->val;
}
};
ListNode *dummy = new ListNode(0);
ListNode *pre = dummy;
priority_queue<ListNode *, vector<ListNode *>, test> q;
for (ListNode *head : lists) {
if (head) {
q.push(head);
}
}
while (!q.empty()) {
ListNode *node = q.top();
q.pop();
pre->next = node;
pre = node;
if (node->next) {
q.push(node->next);
}
}
ListNode *result = dummy->next;
delete dummy;
return result;
}
};
[146] LRU Cache
难度：Medium
语言：C++
题目描述。
使用哈希表+双向链表即可，哈希表指向双向链表中的节点。
哈希表负责完成查找，双向链表负责完成移动（插入或删除）。
class LRUCache {
struct ListNode {
int key;
int val;
ListNode *prev;
ListNode *succ;
ListNode(int key, int val)
: key(key), val(val), prev(nullptr), succ(nullptr) {};
ListNode(int key, int val, ListNode *prev, ListNode *succ)
: key(key), val(val), prev(prev), succ(succ) {};
};
ListNode *dummyHead;
ListNode *dummyTail;
unordered_map<int, ListNode *> umap;
int capacity;
int size;
public:
LRUCache(int capacity) : capacity(capacity) {
dummyHead = new ListNode(-1, 0);
dummyTail = new ListNode(-1, 0);
dummyHead->succ = dummyTail;
dummyTail->prev = dummyHead;
size = 0;
}
ListNode *getNode(int key) {
auto iter = umap.find(key);
if (iter == umap.end()) {
return nullptr;
}
ListNode *node = iter->second;
node->succ->prev = node->prev;
node->prev->succ = node->succ;
node->succ = dummyHead->succ;
node->prev = dummyHead;
dummyHead->succ->prev = node;
dummyHead->succ = node;
return node;
}
int get(int key) {
ListNode *node = getNode(key);
return node ? node->val : -1;
}
void put(int key, int value) {
ListNode *node = getNode(key);
if (!node) {
node = new ListNode(key, value, dummyHead, dummyHead->succ);
dummyHead->succ->prev = node;
dummyHead->succ = node;
size += 1;
umap[key] = node;
if (size > capacity) {
node = dummyTail->prev;
node->prev->succ = dummyTail;
dummyTail->prev = node->prev;
umap.erase(node->key);
delete node;
size -= 1;
}
} else {
node->val = value;
}
}
};