【算法专题九】链表

0.链表常用技巧和操作总结

1.两两相加

1.1 题目

题目链接

1.2 思路

1.3 代码

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

2.两两交换链表中的节点

2.1 题目

题目链接

2.2 思路

2.3 代码

class Solution {
public:ListNode* swapPairs(ListNode* head) {if(head == nullptr || head->next == nullptr) return head;ListNode* newhead = new ListNode(0);newhead->next = head;ListNode* prev = newhead, * cur = head, * next = head->next, * nnext = next->next;while(cur && next){// 交换节点prev->next = next;next->next = cur;cur->next = nnext;// 移动prev、cur、next、nnextprev = cur;cur = nnext;if(cur) next = cur->next;if(next) nnext = next->next;}prev = newhead->next;delete newhead;return prev;}
};

3.leetcode 143.重排链表

3.1 题目

题目链接

3.2 思路

3.3 代码

/*** 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) {// 处理边界情况if(head == nullptr || head->next == nullptr || head->next->next == nullptr) return;// 1. 找到链表的中间节点 - 快慢双指针 （一定要画图考虑 slow 的落点在哪里）ListNode* slow = head, *fast = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;}// 2. 把slow 后面的部分给逆序 - 头插法ListNode* head2 = new ListNode(0);ListNode* cur = slow->next;slow->next = nullptr; // 注意把两个链表给断开while(cur){ListNode* next = cur->next;cur->next = head2->next;head2->next = cur;cur = next;}// 3.合并两个链表 - 双指针ListNode* ret = new ListNode(0);ListNode* prev = ret;ListNode* cur1 = head, *cur2 = head2->next;while(cur1){// 先放第一个链表prev->next =  cur1;cur1 = cur1->next;prev = prev->next;// 再放第二个链表if(cur2){prev->next = cur2;cur2 = cur2->next;prev = prev->next;}}delete head2;delete ret;}
};

4.合并K个升序链表

4.1 题目

题目链接

4.2 思路

4.3 代码

// 方法1：暴力枚举，时间复杂度应该是超时的，不写代码
// 方法2
class Solution {public:struct cmp{bool operator()(ListNode* l1, 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);// 合并K个有序链表ListNode* newHead = new ListNode(0);ListNode* prev = newHead;while(!heap.empty()){ListNode* t = heap.top();heap.pop();prev->next = t;prev = prev->next;if(t->next) heap.push(t->next);}prev = newHead->next;delete newHead;return prev;}
};

// 方法三：归并 递归方法
class Solution {
public:ListNode* mergeKLists(vector<ListNode*>& lists) {return merge(lists, 0, lists.size() - 1);}ListNode* merge(vector<ListNode*>& lists, int left, int right){// 0. 处理边界情况if(left > right) return nullptr;if(left == right) return lists[left];// 1. 平分数组int mid = (left + right) >> 1;// 2. 递归处理左右区间ListNode* l1 = merge(lists, left, mid);ListNode* l2 = merge(lists, mid + 1, right);// 3. 合并两个有序链表return mergeTwoLists(l1, l2); }ListNode* mergeTwoLists(ListNode* l1, ListNode* l2){// 0. 处理边界情况if(l1 == nullptr) return l2;if(l2 == nullptr) return l1;// 1. 合并两个有序链表ListNode head;ListNode* prev = &head;head.next = nullptr;while(l1 && l2){if(l1->val < l2->val){prev = prev->next = l1;if(l1) l1 = l1->next;}else{prev = prev->next = l2;if(l2) l2 = l2->next;}}// 2. 处理剩余的节点if(l1) prev->next = l1;if(l2) prev->next = l2;return head.next;}
};

5.K个一组翻转链表

5.1 题目

题目链接

5.2 思路

5.3 代码

class Solution {
public:ListNode* reverseKGroup(ListNode* head, int k) {// 1.先求有几组kint n = 0;ListNode* cur = head;while(cur){cur = cur->next;n++;}n /= k;// 2.然后进行求解cur = head;ListNode* newHead = new ListNode(0);ListNode* prev = newHead;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;}// 3.处理剩余的部分prev->next = cur;cur = newHead->next;delete newHead;return cur;}
};