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对应的节点。
- 两个指针走过的距离有两倍的关系，可以列方程把