算法笔记（六）——链表

技巧:

1. 画图观察指针指向；
2. 添加虚拟头节点；
3. 可以多定义几个节点；
4. 快慢双指针；

常见操作：

1. 定义new head
2. 逆序时，头插

ListNode* newhead = new ListNode(0);
ListNode* cur= head;
ListNode* next = cur->next;
cur->next = head->next;
head->next = cur;
cur = next

两数相加

题目：两数相加

思路

逆序的链表，只需要一个临时变量来记录进位的值，然后我们可以正常按照计算规则逐个相加直至链表结束

C++代码

/*** 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) {}* };*/
class Solution 
{
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode* newhead = new ListNode(-1);ListNode* prev = newhead;ListNode* cur1 = l1;ListNode* cur2 = l2;int t = 0;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;}
};

两两交换链表中的节点

题目：两两交换链表中的节点

思路

循环终止条件

• 奇节点数，next == NUL
• 偶节点数，cur == NULL

C++代码

/*** 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) {}* };*/
class Solution 
{
public:ListNode* swapPairs(ListNode* head) {if(head == nullptr || head->next == nullptr) return head;ListNode* newhead=new ListNode();newhead->next = head;ListNode* prev = newhead;ListNode* cur = prev->next, *next = cur->next, *nnext = next->next;while(cur && next){// 重新连接节点(顺序无所谓)prev->next = next;next->next = cur;cur->next = nnext;// 迭代节点(注意顺序)prev = cur;cur = nnext;if(cur) next = cur->next;if(next) nnext = next->next;}prev=newhead->next;delete newhead;return prev;}
};

重排链表

题目：重排链表

思路

• 模拟
• 1. 找到链表的中间节点； 快慢双指针
• 2. 逆序后面的链表；头插
• 3. 合并两个链表；双指针

C++代码

/*** 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) {}* };*/
/*** 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) {}* };*/
class Solution 
{
public:void reorderList(ListNode* head) {ListNode* slow = head;ListNode* fast = head->next;while (fast && fast->next) {slow = slow->next;fast = fast->next->next;}//反转后半段链表ListNode* second = reverseList(slow->next);slow->next = nullptr;ListNode* first = head;//交替合并first和secondwhile (second) {ListNode* tmpNode1 = first->next;ListNode* tmpNode2 = second->next;first->next = second;second->next = tmpNode1;first = tmpNode1;second = tmpNode2;}}ListNode* reverseList(ListNode* head) {if (head == nullptr) return head;ListNode* prev = nullptr;ListNode* cur = head;while (cur){ListNode* tmp = cur->next;cur->next = prev;prev = cur;cur = tmp;}return prev;}
};

合并 K 个升序链表

题目：合并 K 个升序链表

思路

• 将每个链表的头节点入小堆，每次从堆顶元素开始链接，逐个将堆顶的最小链表节点链接，并不断向堆中添加后续元素；

C++代码

/*** 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) {}* };*/
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* ret = new ListNode(0);ListNode* prev = ret;while(!heap.empty()){ListNode* t = heap.top();heap.pop();prev->next = t;  prev = t;if(t->next != nullptr) heap.push(t->next);}prev = ret->next;delete ret;return prev;}
};

K个一组翻转链表

题目：K 个一组翻转链表

思路

• 计算需要翻转的次数
• 重复 n 次，长度为 k 的链表的逆序

C++代码

/*** 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) {}* };*/
class Solution 
{
public:ListNode* reverseKGroup(ListNode* head, int k) {// 统计节点个数int n = 0;ListNode* cur = head;while(cur){n++;cur = cur->next;}n /= k;// 重复n次长度为k的链表逆序ListNode* newhead = new ListNode(0);ListNode* prev = newhead;cur = head;for(int i = 0; i < n; i++){ListNode* tmp = cur;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;return newhead->next;}
};