链表基础
基本结构与操作
/**
* Definition for singly-linked list.
* 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) {}
* };
*/
环形链表判断
题目 定义两个指针，一快一慢。慢指针每次只移动一步，而快指针每次移动两步。初始时，慢指针在位置 head，而快指针在位置 head.next。这样一来，如果在移动的过程中，快指针反过来追上慢指针，就说明该链表为环形链表。否则快指针将到达链表尾部，该链表不为环形链表。
bool hasCycle(ListNode* head) {
// 空链表，以及单个节点无法设置快指针
if (head == nullptr || head->next == nullptr) {
return false;
}
ListNode* slow = head;
ListNode* fast = head->next;
while (slow != fast) {
// 快指针走到结尾，说明无环，注意确认下下个的存在性
if (fast == nullptr || fast->next == nullptr) {
return false;
}
// 龟兔赛跑，快指针每次夺走
slow = slow->next;
fast = fast->next->next;
}
return true;
}
反转链表
反转完整链表 定义两个指针： pre 和 cur ；pre 在前 cur 在后。 每次让 pre 的 next 指向 cur ，实现一次局部反转 局部反转完成之后，pre 和 cur 同时往前移动一个位置 循环上述过程，直至 pre 到达链表尾部
ListNode* reverseList(ListNode* head) {
ListNode* cur = NULL, *pre = head;
while (pre != NULL) {
ListNode* t = pre->next;
pre->next = cur;
cur = pre;
pre = t;
}
return cur;
}
void reverseLinkedList(ListNode *head) {
// 也可以使用递归反转一个链表
ListNode *pre = nullptr;
ListNode *cur = head;
while (cur != nullptr) {
ListNode *next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
}
ListNode *reverseBetween(ListNode *head, int left, int right) {
// 因为头节点有可能发生变化，使用虚拟头节点可以避免复杂的分类讨论
ListNode *dummyNode = new ListNode(-1);
dummyNode->next = head;
ListNode *pre = dummyNode;
// 第 1 步：从虚拟头节点走 left - 1 步，来到 left 节点的前一个节点
// 建议写在 for 循环里，语义清晰
for (int i = 0; i < left - 1; i++) {
pre = pre->next;
}
// 第 2 步：从 pre 再走 right - left + 1 步，来到 right 节点
ListNode *rightNode = pre;
for (int i = 0; i < right - left + 1; i++) {
rightNode = rightNode->next;
}
// 第 3 步：切断出一个子链表（截取链表）
ListNode *leftNode = pre->next;
ListNode *curr = rightNode->next;
// 注意：切断链接
pre->next = nullptr;
rightNode->next = nullptr;
// 第 4 步：反转链表的子区间
reverseLinkedList(leftNode);
// 第 5 步：接回到原来的链表中
pre->next = rightNode;
leftNode->next = curr;
return dummyNode->next;
}
合并链表
合并两个升序链表 递归法： 
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
if (list1 == NULL) {
return list2;
}
if (list2 == NULL) {
return list1;
}
if (list1->val <= list2->val) {
list1->next = mergeTwoLists(list1->next, list2);
return list1;
}else{
list2->next = mergeTwoLists(list1, list2->next);
return list2;
}
}
遍历法：
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* preHead = new ListNode(-1);
ListNode* prev = preHead;
while (l1 != nullptr && l2 != nullptr) {
if (l1->val < l2->val) {
prev->next = l1;
l1 = l1->next;
} else {
prev->next = l2;
l2 = l2->next;
}
prev = prev->next;
}
// 合并后 l1 和 l2 最多只有一个还未被合并完，直接将链表末尾指向未合并完的链表即可
prev->next = l1 == nullptr ? l2 : l1;
return preHead->next;
}
[合并k个升序链表] 适合练习讨论所有情况
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
if (list1 == NULL) {
return list2;
}
if (list2 == NULL) {
return list1;
}
if (list1->val <= list2->val) {
list1->next = mergeTwoLists(list1->next, list2);
return list1;
}else{
list2->next = mergeTwoLists(list1, list2->next);
return list2;
}
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
if(lists.size() == 0) {
return NULL;
}
if(lists.size() == 1) {
return lists[0];
}
int initial;
ListNode* ans = NULL;
for (initial = 0; initial < lists.size() - 1; initial++) {
if(lists[initial] == NULL){
cout << initial;
}
if(lists[initial] != NULL){
cout << initial;
break;
}
}
for (int i = initial + 1; i < lists.size(); i++) {
lists[initial] = mergeTwoLists(lists[initial], lists[i]);
}
return lists[initial];
}
优化思路为分治：
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode dummy{}; // 用哨兵节点简化代码逻辑
auto cur = &dummy; // cur 指向新链表的末尾
while (list1 && list2) {
if (list1->val < list2->val) {
cur->next = list1; // 把 list1 加到新链表中
list1 = list1->next;
} else { // 注：相等的情况加哪个节点都是可以的
cur->next = list2; // 把 list2 加到新链表中
list2 = list2->next;
}
cur = cur->next;
}
cur->next = list1 ? list1 : list2; // 拼接剩余链表
return dummy.next;
}
// 合并从 lists[i] 到 lists[j-1] 的链表
ListNode* mergeKLists(vector<ListNode*>& lists, int i, int j) {
int m = j - i;
if (m == 0) {
return nullptr; // 注意输入的 lists 可能是空的
}
if (m == 1) {
return lists[i]; // 无需合并，直接返回
}
auto left = mergeKLists(lists, i, i + m / 2); // 合并左半部分
auto right = mergeKLists(lists, i + m / 2, j); // 合并右半部分
return mergeTwoLists(left, right); // 最后把左半和右半合并
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
return mergeKLists(lists, 0, lists.size());
}
不用递归写法，可以用迭代写法，避免栈过深：
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode dummy{}; // 用哨兵节点简化代码逻辑
auto cur = &dummy; // cur 指向新链表的末尾
while (list1 && list2) {
if (list1->val < list2->val) {
cur->next = list1; // 把 list1 加到新链表中
list1 = list1->next;
} else { // 注：相等的情况加哪个节点都是可以的
cur->next = list2; // 把 list2 加到新链表中
list2 = list2->next;
}
cur = cur->next;
}
cur->next = list1 ? list1 : list2; // 拼接剩余链表
return dummy.next;
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
int m = lists.size();
if (m == 0) {
return nullptr;
}
for (int step = 1; step < m; step *= 2) {
for (int i = 0; i < m - step; i += step * 2) {
lists[i] = mergeTwoLists(lists[i], lists[i + step]);
}
}
return lists[0];
}