文章目录
1. 常用技巧 && 操作
下面的技巧通过一些后面的例题可以较好的理解熟练。
常用技巧
- 画图
- 链表题通过画图可以较为直观分析链表，方便分析如何进行对链表的操作等
- 引入虚拟“头”节点
- 虚拟节点适合处理一些边界情况
- 同时放便我们进行对链表的操作
- 多定义变量
- 多定义变量增强可读性，也方便自己写代码时的思路
- 如当频繁使用cur节点的next时，直接定义 ListNode* next = cur->next; 不用再频繁对cur->next进行操作（这个例子较为简单，对于偏复杂的情况有大优点）
- 不用过于在意这一点空间开销
- 双指针
- 如快慢双指针可以解决链表判环、找环入口等。
- 常用操作
- 头插 - “反转链表等题，可以解题”
- 尾插
2. 根据技巧 小试牛刀
下面的题目难度不算太高，就用文字描述的形式解释思路、原理。
141.环形链表
思路
解法：即前面介绍过的快慢双指针。
解法原理：快指针每次移动两步，而慢指针每次移动一步。如果链表中存在环，那么快指针相对于慢指针的速度差是一定的，因此快指针会逐渐靠近慢指针，最终追上它们。如果链表中不存在环，那么快指针会先到达链表的末尾。
代码
bool hasCycle(ListNode *head) {
// 快慢指针
ListNode* slow = head, *fast = head;
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if(slow == fast) return true;
}
return false;
}
142.环形链表II
思路
- 解法：快慢双指针
- 同理我们首先 判断链表是否存在环
- 当链表存在环则：
- 让相遇位置节点与头节点依次向后移，直到两节点相遇
- （也可以将慢指针重新指向头节点，随后快慢指针依次后移一步）
原理分析：我们设链表头节点到环入口节点的距离为a，环入口节点到相遇节点的距离为b，相遇节点到环入口节点的距离为c，则有以下关系：快指针走过的距离是慢指针的两倍，即2(a+b)=a+b+c+b，化简得到a=c。因此，在快慢指针相遇之后，让快指针重新指向头节点，然后快慢指针同时以相同的速度向前移动，当它们再次相遇时所在的节点就是环的入口节点。
代码
ListNode *detectCycle(ListNode *head) {
if(head == nullptr || head->next == nullptr) return nullptr;
ListNode* slow = head, *fast = head;
// 先判断是否有环
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if(slow == fast)
{
ListNode* meet = slow; // 相遇位置设为meet
while(meet != head)
{
head = head->next;
meet = meet->next;
}
return meet;
}
}
return nullptr;
}
19.删除链表的倒数第N个结点
思路
- 解法：快慢双指针
- 让快指针向前移动n步，使得快指针与慢指针之间相隔n个节点。
- 同时移动快指针和慢指针，直到 fast到达链表的末尾 （即为空）。此时slow指向的节点就是要删除的节点的前一个节点 （倒数第n-1）。
- 此时将slow指向的节点的next指针指向下下个节点，即跳过待删除节点。
代码
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* PNode = new ListNode(0); // 虚拟头节点
PNode->next = head;
ListNode* slow = PNode, *fast = PNode;
// fast先走n+1步
for(int i = 0; i < n+1; ++i)
fast = fast->next;
// 两指针同步走
while(fast)
{
slow = slow->next;
fast = fast->next;
}
// 此时slow就是倒数第n-1节点
slow->next = slow->next->next;
return PNode->next;
}
LCR024.反转链表
思路
- 解法：虚拟头指针+头插
- 我们首先创建虚拟头指针newhead，作为最终反转后的链表头节点
- 通过将原链表中的节点依次提取头插到新链表中，当cur指向空，此时newhead就是新链表的头
代码
ListNode* reverseList(ListNode* head) {
ListNode* newhead = nullptr; // 虚拟头指针
ListNode* cur = head;
// 利用头插翻转
while(cur)
{
ListNode* next = cur->next;
cur->next = newhead;
newhead = cur;
cur = next;
}
return newhead;
}
3. 解决算法题
2.两数相加
思路
如上图所示：
代码
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
int t = 0; // 记录相加和
ListNode* newhead = new ListNode(0); // 虚拟头节点
ListNode* cur1 = l1, *cur2 = l2; // 用于遍历链表
ListNode* prev = newhead; // 尾指针
while(cur1 || cur2 || t)
{
// 相加并移动指针
if(cur1){
t += cur1->val;
cur1 = cur1->next;
}
if(cur2){
t += cur2->val;
cur2 = cur2->next;
}
// 更新结果
prev->next = new ListNode(t % 10);
prev = prev->next;
t /= 10;
}
// 释放空间
prev = newhead->next;
delete newhead;
return prev;
}
24.两两交换链表中的节点
思路
这里我们提供两种解法：① 递归 ② 循环（模拟过程）
解法一：递归
- 根据图中思路，两两交换节点后，新头节点应该是之前在后面的节点
- 我们首先记录新头节点节点，后更改指针朝向，将新头节点的next指向下一位的新头节点
- 函数的返回结果就是每次的新头节点，利用递归即tmp = swapPairs(head->next->next)，即交换后面的节点并每次链接新头节点
代码
ListNode* swapPairs(ListNode* head) {
if(head == nullptr || head->next == nullptr)
return head;
// 递归
auto tmp = swapPairs(head->next->next); // 翻转后的前一位节点
auto ret = head->next; // 新头节点
head->next->next = head; // 更改指针指向
head->next = tmp;
return ret;
}
解法二：循环
- 思路如图所示，我们首先定义四个指针（首先创建一个虚拟头节点）
- 根据四个指针位置可以完成交换节点，移动指针的操作
- cur代表每一轮待交换的指针，当在一轮交换后，我们进行指针位置修正
- 直到cur、next任意一方为空，结束循环
代码
ListNode* swapPairs(ListNode* head) {
if(head == nullptr || head->next == nullptr)
return head;
ListNode* prev = new ListNode(0);
ListNode* cur = head;
ListNode* next = cur->next, *nnext = next->next;
head = next; // 一轮交换后,head会到第二位，修正位置
while(cur && next) // cur与next都不为空时才进行交换
{
// 两两交换操作
prev->next = next;
next->next = cur;
cur->next = nnext;
// 移动指针
prev = cur;
cur = nnext;
next = cur ? cur->next : nullptr;
nnext = next ? next->next : nullptr;
}
return head;
}
143.重排链表
思路
- 题目要求将链表按照规则重拍
- 我们可以按照以下思路执行（以链表[1, 2, 3, 4, 5]举例）：
- 将链表从中点处分开 1 2 3 与 4 5
- 将中点后的链表逆序 5 4
- 合并两链表 1 2 3 + 5 4 = 1 5 2 4 3
代码
void reorderList(ListNode* head) {
if(!head || !head->next || !head->next->next) return;
// 1. 找到链表中点
ListNode* slow = head, *fast = head;
while(fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
// 2. 翻转中点后的节点
ListNode* newhead = nullptr;
ListNode* cur = slow->next;
while(cur)
{
ListNode* next = cur->next;
cur->next = newhead;
newhead = cur;
cur = next;
}
slow->next = nullptr; // 切断前半部分与后半部分的连接
// 3. 合并链表（123 与 54 -> 1 5 2 4 3）
ListNode* cur1 = head, *cur2 = newhead;
while(cur1 && cur2) {
ListNode* next1 = cur1->next, *next2 = cur2->next;
cur1->next = cur2;
cur2->next = next1;
cur1 = next1;
cur2 = next2;
}
}
23.合并K个升序链表
思路
- 解法：小根堆
- 细节注意：创建小根堆时需要用自定义比较，下面我们使用自定义比较结构体、也可以使用lambda表达式
代码
class Solution {
public:
struct cmp // 自定义比较
{
bool operator()(const ListNode* l1, const ListNode* l2){
return l1->val > l2->val;
}
};
ListNode* mergeKLists(vector<ListNode*>& lists) {
priority_queue<ListNode*, vector<ListNode*>, cmp> heap; // 创建小根堆
for(auto l : lists)
if(l) heap.push(l); // 将所有插入到堆中
// 合并链表
ListNode *head = new ListNode(0);
ListNode *prev = head;
while(!heap.empty()) // 堆有元素时，进行操作
{
ListNode* tmp = heap.top();
heap.pop();
prev->next = tmp; // 更新链表链接关系和prev
prev = tmp;
if(tmp->next) heap.push(tmp->next);
}
prev = head->next;
delete head;
return prev;
}
};
25.K个一组翻转链表
思路
代码
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
ListNode* cur = head;
int n = 0; // 记录待翻转链表个数
while(cur)
{
cur = cur->next;
n++;
}
n /= k;
ListNode* newhead = new ListNode(0);
ListNode* prev = newhead;
cur = head;
// 进行链表的分组旋转 n组 每组k个节点
for(int i = 0; i < n; ++i)
{
ListNode* tmp = cur; // tmp记录每次待翻转链表的头节点
for(int j = 0; j < k; ++j)
{
ListNode* next = cur->next;
cur->next = prev->next;
prev->next = cur;
cur = next;
}
prev = tmp; //
}
// 剩余不必翻转的，添加到链表中
prev->next = cur;
// 删除newhead释放空间
cur = newhead->next;
delete newhead;
return cur;
}
};
