一、链表常用技巧和操作总结
有关链表的算法题是一类常见并且经典的题型，这些题要使用数据结构中手搓的链表结构，也要使用 STL 中的 list 容器。
下面是几点常用操作的总结：
- 善于画图。
- 引入虚拟头结点。方便处理边界情况，就是当没有节点第一次头插或尾插的时候的那个判断，引入虚拟头结点就可以避免这个判断（写成
ptail = newHead）。 - 不要吝啬空间，大胆定义变量。
- 快慢双指针的使用。主要应用是判环，找链表中环的入口，找链表中倒数第 n 个节点。
- 解决链表类的题，一般是：创建一个新节点，尾插操作，头插操作。
二、算法原理和代码实现
2. 两数相加
算法原理：
这道题是一道简单的模拟题，模拟两数相加即可。定义两个指针 cur1 和 cur2 用于遍历两个链表，再定义一个整数 t 用于进位。用 t 和每个节点的值相加，取出 t 的个位创建新节点。
细节问题：
- 这里要注意的细节就是链表是逆序的，其实这也是方便我们操作，因为我们可以直接从个位开始相加。
- 循环条件：
cur1 || cur2 || t。这里要或 t 是原因：当两个指针都走完时，t 里可能还有进位，还需要尾插。 - 要销毁哨兵位头节点。
代码实现：
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* cur1 = l1, *cur2 = l2;
ListNode* newHead = new ListNode(), *ptail = newHead; // 虚拟头节点
int t = 0; // 记录进位
while (cur1 || cur2 || t) {
if (cur1) { t += cur1->val; cur1 = cur1->next; }
if (cur2) { t += cur2->val; cur2 = cur2->next; }
ListNode* newNode = new ListNode(t % 10);
ptail->next = newNode;
ptail = newNode;
ptail->next = nullptr;
t /= 10;
}
ListNode* pcur = newHead->next;
delete newHead;
return pcur;
}
};
24. 两两交换链表中的节点
算法原理：
本题也是一道模拟题，重点是画图，看图写代码!!! 定义四个指针： 根据交换后的链表，进行指针的修改（绿色字），一直循环迭代。 结束条件：
- 偶数个节点时：cur 已经指向空了，next 和 nnext 也无效了，此时结束循环。
- 奇数个节点时：next 已经指向空了，nnext 无效了，此时也结束循环。
代码实现：
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
if (head == nullptr) return nullptr;
ListNode* newHead = new ListNode(), *prev = newHead;
ListNode* cur = head, *next = cur->next;
ListNode* nnext = nullptr;
if (next) nnext = next->next;
prev->next = cur;
while (cur && next) {
// 交换节点
prev->next = next;
next->next = cur;
cur->next = nnext;
// 修改指针
prev = cur;
cur = prev->next;
if (cur) next = cur->next;
if (next) nnext = next->next;
}
ListNode* pcur = newHead->next;
delete newHead;
return pcur;
}
};
143. 重排链表
算法原理：
这道题比较有综合性，通过分析可以发现：重排后的链表 = 合并两个链表 (原链表的前半段 + 原链表的后半段逆置)。 所以这道题的思路是：
- 找到链表的中间节点。
- 把后半部分逆序。
- 合并两个链表。
代码实现：
class Solution {
public:
// 找中间节点
ListNode* FindMiddleNode(ListNode* head) {
ListNode* slow = head, *fast = head, *prev = head;
while (fast && fast->next) {
prev = slow;
slow = slow->next;
fast = fast->next->next;
}
prev->next = nullptr; // 与后半段断开
return slow;
}
// 逆置后半部分链表
ListNode* reverseList(ListNode* head) {
ListNode* phead = head, *ptail = nullptr;
while (phead) {
ListNode* next = phead->next; // 头插法
phead->next = ptail;
ptail = phead;
phead = next;
}
return ptail;
}
void reorderList(ListNode* head) {
// 处理特殊情况
if (head->next == nullptr || head->next->next == nullptr) return;
ListNode* mNode = FindMiddleNode(head);
ListNode* rNode = reverseList(mNode); // 合并两个链表
ListNode* newHead = new ListNode(), *ptail = newHead;
ListNode* n1 = head, *n2 = rNode;
while (n1 && n2) {
ptail->next = n1;
ptail = ptail->next;
n1 = n1->next;
ptail->next = n2;
ptail = ptail->next;
n2 = n2->next;
}
if (n1) ptail->next = n1;
if (n2) ptail->next = n2;
delete newHead;
}
};
23. 合并 k 个升序链表
算法原理：
解法 1：暴力解法，利用'合并两个有序链表'的思想。先把第一个和第二个链表进行合并，得到一个新链表，再用新链表和第三个链表进行合并…。假设有 k 个链表，每条链表的平均节点有 n 个，则时间复杂度为：n(k-1) + n(k-2) + n(k-3) + … + n --> O(n * k^2)。大概率超时。
解法 2：利用优先级队列进行优化。假设有 k 个链表，建一个大小为 k 的小根堆，把所有链表的第一个节点都扔进小根堆中，堆顶节点就是最小值，取出堆顶节点和虚拟头结点进行链接，再移到下一个节点…合并链接 + 找出最小值的节点总的时间复杂度为：O(n * k * logk)。
易错/细节问题：
- 优先级队列的第三个模板参数不能直接写成
greater<ListNode*>，因为这样比较的是地址，要写一个仿函数!! - 把链表的所有头节点都入队列时，要注意传递的链表为空的处理。
代码实现：
class Solution {
struct cmp {
bool operator()(const ListNode* l1, const ListNode* l2) {
return l1->val > l2->val;
}
};
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
// 建小根堆
priority_queue<ListNode*, vector<ListNode*>, cmp> pq;
// 把所有头结点进小根堆
for (auto l : lists)
if (l) pq.push(l);
// 合并 k 个有序链表
ListNode* newhead = new ListNode(), *ptail = newhead;
while (!pq.empty()) {
ListNode* pcur = pq.top();
pq.pop();
ptail->next = pcur;
ptail = pcur;
if (pcur->next) pq.push(pcur->next);
}
ListNode* ret = newhead->next;
delete newhead;
return ret;
}
};
解法 3：分治 - 递归。和归并分治的思想一样：假设有 k 个链表，那么就有 logk 层，递归回退时每个链表的每个节点都执行 logk 次合并，每个链表的平均节点有 n 个，所以时间复杂度为：O(n * k * logk)。
易错/细节问题：
- 有两个递归出口：区间不存在和区间里只有一个链表。
- 合并两个有序链表时，链表为空的情况。
代码实现：
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
return merge(lists, 0, lists.size() - 1);
}
ListNode* merge(vector<ListNode*>& lists, int left, int right) {
if (left > right) return nullptr;
if (left == right) return lists[left];
// 找中点
int mid = left + (right - left) / 2;
// [left, mid] [mid+1, right]
// 合并左右两边
ListNode* l1 = merge(lists, left, mid);
ListNode* l2 = merge(lists, mid + 1, right);
// 合并两个有序链表
return mergeTwoList(l1, l2);
}
ListNode* mergeTwoList(ListNode* l1, ListNode* l2) {
// 处理特殊情况
if (l1 == nullptr) return l2;
if (l2 == nullptr) return l1;
ListNode head; // 把虚拟节点开在栈上
head.next = nullptr;
ListNode* ptail = &head;
while (l1 && l2) {
if (l1->val < l2->val) {
ptail->next = l1;
ptail = ptail->next;
l1 = l1->next;
} else {
ptail->next = l2;
ptail = ptail->next;
l2 = l2->next;
}
}
if (l1) ptail->next = l1;
if (l2) ptail->next = l2;
return head.next;
}
};
25. k 个一组翻转链表
算法原理：
这也是一道模拟题，算法流程比较简单：
- 先求出需要逆序多少组：n。
- 重复 n 次，长度为 k 的链表的逆序即可。
- 把不需要逆序的接上。
细节问题：
- 这里需要记录第 n 次头插的开始位置，每次进行新一轮逆序时都要记住该位置。
- 如果使用 while 循环，则每逆序完一组后 k 要重新赋值，不然就一直都是 k==0 了。
代码实现：
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
// 先求出要逆序多少组
int n = 0;
ListNode* phead = head;
while (phead) {
phead = phead->next;
n++;
}
n /= k; // 重复 n 次长度为 k 的链表逆序
phead = head;
ListNode* newhead = new ListNode(), *prev = newhead;
for (int i = 0; i < n; i++) {
ListNode* tmp = phead; // 记录每一组的起点
for (int j = 0; j < k; j++) {
ListNode* next = phead->next;
phead->next = prev->next;
prev->next = phead;
phead = next;
}
prev = tmp;
}
// 把不需要翻转的接上
prev->next = phead;
ListNode* ret = newhead->next;
delete newhead;
return ret;
}
};
三、算法总结
通过上面的若干道题目可以发现，大多数链表类的题目本质上是模拟题，最重要的就是画图，分清各个指针指向哪里。