优先算法——专题九：链表

一、两数相加

2. 两数相加 - 力扣（LeetCode）

/*** 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* head = new ListNode(0), * tail = head;ListNode* cur1 = l1, * cur2 = l2;int t = 0;//表示进位while (cur1 || cur2){int num1 = cur1 ? cur1->val : 0;int num2 = cur2 ? cur2->val : 0;int sum = num1 + num2 + t;t = sum / 10;//进位，用作下一次的相加sum %= 10;ListNode* node = new ListNode(sum);tail->next = node;tail = tail->next;if (cur1)cur1 = cur1->next;if (cur2)cur2 = cur2->next;}//进位可能不为0，还要继续if (t > 0){ListNode* node = new ListNode(t);tail->next = node;tail = tail->next;}tail = head->next;delete head;//防止内存泄漏return tail;}
};

二、两两交换链表中的节点

24. 两两交换链表中的节点 - 力扣（LeetCode）

/*** 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(-1), *newtail = newhead;ListNode *cur1 = head, *cur2 = cur1->next, *next = cur2->next;while(cur1 && cur2){newtail->next = cur2;cur2->next = cur1;cur1->next = next;newtail = cur1;cur1 = newtail->next;if(cur1 == nullptr) break;//偶数循环结束cur2 = cur1->next;if(cur2 == nullptr) break;//奇数循环结束next = cur2->next;}newtail = newhead->next;delete newhead;//防止内存泄漏return newtail;}
};

三、重排链表

143. 重排链表 - 力扣（LeetCode）

/*** 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:
//本道题实际上就是就是前面一半链表和后面一半的逆序链表进行连接//1、找到中间节点//2、从中间节点分为两部分，后面一部分的链表进行逆序重排//3、将两个链表进行连接，使用双指针的方法void reorderList(ListNode* head) {if(head->next == nullptr) return;//1、找到中间节点ListNode *slow = head, *fast = slow;ListNode *prev = head;//记录中间节点前的一个节点while(fast && fast->next){prev = slow;slow = slow->next;fast = fast->next;fast = fast->next;}//出来slow为中间节点//2、进行后半部分链表的逆序prev->next = nullptr;//将两部分链表分开ListNode *p = nullptr, *c = slow, *n = c->next;while(c){c->next = p;p = c;c = n;if(c)n = c->next;}//出来p为逆序链表的头节点//3、进行两个链表的连接ListNode* cur1 = head, *next1 = cur1->next, *cur2 = p, *next2 = cur2->next;while(next1 && next2){cur1->next = cur2;cur2->next = next1;cur1 = next1;cur2 = next2;next1 = cur1->next;next2 = cur2->next;}if(!next1 && next2)//奇数情况{cur1->next = cur2;cur2->next = next2;}if(!next1 && !next2)//偶数情况{cur1->next = cur2;}}
};

四、合并k个升序链表

23. 合并 K 个升序链表 - 力扣（LeetCode）

解法一：利用小根堆，先将所有的链表的头节点入堆，之后取出堆顶的节点插入链表，下一次入堆的节点是这个堆顶节点在原链表中的下一个节点，当所有链表为空时结束

时间复杂度：k个链表，每个链表n个节点，优先级队列增删查改是logn，那么就是n*k*logk（大小为k的小堆，共有n*k个节点，每个节点都要参与）

/*** 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) {if(lists.size()==0) return nullptr;priority_queue<ListNode*, vector<ListNode*>, cmp> myqueue;//头节点入队列for(auto l : lists){if(l)//不能为空myqueue.push(l);}ListNode *head = new ListNode (-1);ListNode *cur = head;while(!myqueue.empty()){ListNode *top = myqueue.top();myqueue.pop();cur->next = top;cur = cur->next;if(top && top->next) myqueue.push(top->next);}cur = head->next;delete head;return cur;}
};

解法二：使用分治递归-归并的思想；先分，分到两个链表的合并，之后“归”，将合并好的两个链表合并

时间复杂度：k个链表，“归”的时候有logk层，那么每个链表就要归logk次，归的时候实际上是节点参与比较（链表合并），那么就是n*k*logk。（“递”的时候没有节点比较，算是“小头”）

class Solution 
{
public:ListNode* mergeKLists(vector<ListNode*>& lists) {//归并：要先算好中间的分割位置，所以要传边界return _mergeKLists(lists, 0, lists.size()-1);    }ListNode* _mergeKLists(vector<ListNode*>& lists, int left, int right){if(left > right) return nullptr;if(left == right) return lists[left];int mid = left + (right - left) / 2;//“递”，直到链表个数为2开始合并ListNode *l1 = _mergeKLists(lists, left, mid);ListNode *l2 = _mergeKLists(lists, mid+1, right);return mergetwolists(l1, l2);}ListNode* mergetwolists(ListNode* l1, ListNode* l2){//两个链表进行合并if(l1 == nullptr) return l2;if(l2 == nullptr) return l1;ListNode *head = new ListNode (-1);ListNode *tail = head, *cur1 = l1, *cur2 = l2;while(cur1 && cur2){if(cur1->val <= cur2->val){tail->next = cur1;tail = tail->next;cur1 = cur1->next;}else{tail->next = cur2;tail = tail->next;cur2 = cur2->next;                }}while(cur1){tail->next = cur1;tail = tail->next;cur1 = cur1->next;            }while(cur2){tail->next = cur2;tail = tail->next;cur2 = cur2->next;            }       tail = head->next;delete head;return tail;}
};

五、k个一组翻转链表

25. K 个一组翻转链表 - 力扣（LeetCode）

先算出链表中有多少个k组，之后再对每一组进行逆序，剩下的不足k个的节点直接连接在后面

/*** 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) {//1、遍历链表得出长度，算出有多少个k组ListNode *cur = head;int count = 0;while(cur){++count;cur = cur->next;}int group_cnt = count / k;//2、进行group_cnt次逆序，每次逆序的节点个数为kListNode *newhead = new ListNode (-1);//cur遍历链表，tail头插的固定节点，prev为tail的更新参照cur = head;ListNode *prev = cur, *tail = newhead;for(int i = 0; i < group_cnt; i++){//记录下一个节点方便逆序ListNode *next = cur;for(int j = 0; j < k; j++){next = cur->next;cur->next = tail->next;tail->next = cur;cur = next;}tail = prev;//更新固定头节点prev = cur;//下一次的逆序的固定头节点}//3、不足k个的剩余节点尾插while(cur){tail->next = cur;tail = tail->next;cur = cur->next;}ListNode *ret = newhead->next;delete newhead;return ret;}
};