算法专题八: 链表

链表

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

• 常用技巧

1. 画图!!! 更加直观形象, 便于我们理解
2. 引入虚拟头节点, 方便我们对链表的操作, 减少我们对边界情况的考虑. 如果没有虚拟头节点我们可能还需要考虑头插时候的情况进行特殊处理

3. 不要吝啬空间, 大胆定义变量
4. 快慢双指针, (判环, 找链表中环的入口, 找链表中倒数第n个节点)

• 链表中的常用操作

1. 创建一个新的节点 使用new
2. 尾插的方法
3. 头插的方法 (逆序链表)

---

2. 两数相加

算法原理:

模拟两数相加的过程即可, 使用头插, 取l1的数, l2的数, 累加到t中.

编写代码:

/*** 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;ListNode* prev = newhead;ListNode* cur1 = l1, *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;}ListNode* add = new ListNode(t % 10);prev = prev->next = add;t /= 10;}prev = newhead->next;delete newhead;return prev;}
};

---

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

算法思路: 方法一是使用递归的方法, 方法二就是使用模拟

不要吝啬指针的定义只要我们定义好了上述指针就会发现仅需遍历一遍链表即可讲链表进行交换, 先进行交换, 这里需要修改到三个指针, 如果为偶数的情况下cur和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:ListNode* swapPairs(ListNode* head) {if(head == nullptr || head->next == nullptr) return head;ListNode* newhead = new ListNode;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;cur = nnext;if(cur) next = cur->next;if(next) nnext = next->next;}cur = newhead->next;delete newhead;return cur;}
};

---

4. 重排链表

算法思路:

这里把slow后面的部分逆序有两种策略, 第一种包括slow位置, 第二种slow->next的位置进行逆序, 如果按照第二种可以直接slow->next = nullptr讲链表置为空, 如果第一种想要将链表置空需要遍历的时候记录一下位置, 这里我们采用第二种方式只把slow->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) {if(head == nullptr || head->next == nullptr || head->next->next == nullptr) return;ListNode* fast = head, *slow = head;while(fast && fast->next){fast = fast->next->next;slow = slow->next;}ListNode* cur = slow->next;slow->next = nullptr; ListNode* prev = nullptr;while(cur){ListNode* next = cur->next;cur->next = prev;prev = cur;cur = next;}ListNode* l1 = head;ListNode* l2 = prev;ListNode* newhead = new ListNode; prev = newhead;while(l1){prev = prev->next = l1;l1 = l1->next;if(l2){prev = prev->next = l2;l2 = l2->next;}}delete newhead;}
};

---

/*** 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; //处理边界情况ListNode* fast = head, *slow = head;while(fast && fast->next){fast = fast->next->next;slow = slow->next;}//头插法进行逆置slow->next后面的部分ListNode* head2 = new ListNode;ListNode* cur = slow->next;slow->next = nullptr;//断开链表while(cur){ListNode* next = cur->next;cur->next = head2->next;head2->next = cur;cur = next;}//合并两个链表尾插ListNode* cur1 = head, *cur2 = head2->next;ListNode* ret = new ListNode;ListNode* prev = ret;while(cur1){prev->next = cur1;prev = prev->next; cur1 = cur1->next;if(cur2){prev->next = cur2;prev = prev->next;cur2 = cur2->next;}}delete ret;delete head2;return;   }
};

---

5. 合并K个升序链表

算法思路:

暴力解法时间复杂度太高了, 而且比较麻烦

1. 模拟, 使用堆这个数据结构, 重载比较函数, 先将所有的头节点插入到堆中, 然后取堆顶元素进行合并, 合并之后如果下一个元素存在把下一个元素插入到堆中, 如果堆为空则合并完毕, 注意这里的const修饰的是指针本身, 而不是修饰这个变量, 因为这个变量不是const类型变量, const位置放置错误会导致报错, 注意类型匹配.

/*** 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:class com{public:bool operator()(ListNode* const &l1, ListNode* const &l2){return l1->val > l2->val;}};ListNode* mergeKLists(vector<ListNode*>& lists) {priority_queue<ListNode*, vector<ListNode*>,com> heap;for(auto x : lists)if(x) heap.push(x);ListNode* newhead =new ListNode;ListNode* prev = newhead;while(!heap.empty()){ListNode* t = heap.top();prev = prev->next = t;heap.pop();if(t->next) heap.push(t->next);}prev = newhead->next;delete newhead;return prev;}
};

2. 递归

/*** 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* mergeKLists(vector<ListNode*>& lists) {return mergeSort(lists,0,lists.size()-1);}ListNode* mergeSort(vector<ListNode*>& lists,int left,int right){//处理边界if(left > right) return nullptr;if(left == right) return lists[left];//划分区间int mid = (right + left) >> 1;ListNode* l1 = mergeSort(lists, left, mid);ListNode* l2 = mergeSort(lists,mid+1, right);//排列return mergelist(l1,l2);}ListNode* mergelist(ListNode* l1, ListNode* l2){if(l1 == nullptr) return l2;if(l2 == nullptr) return l1;ListNode* newhead = new ListNode;ListNode* prev = newhead;while(l1 && l2){if(l1->val < l2->val){prev = prev->next = l1;l1 = l1->next;}else{prev = prev->next = l2;l2 = l2->next;}}if(l1) prev->next = l1;if(l2) prev->next = l2;prev = newhead->next;delete newhead;return prev;}
};

---

6. 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) {ListNode* cur = head; int n = 0;while(cur){cur = cur->next;n++;}n /= k;ListNode* newhead = new ListNode;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;cur = newhead->next;delete newhead;return cur;}
};

---

完