算法练习——链表

一：两数相加

题目要求：

解题思路：

思路：注意进位即可

实现代码：

    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode* cur1 = l1, * cur2 = l2;ListNode* phead = new ListNode(0);ListNode* cur = phead;int sum = 0;while(cur1 || cur2 || sum) {//除了两个链表中的数外，还要考虑进位，只要存在进位就要加if(cur1) {sum += cur1->val;cur1 = cur1->next;}if(cur2) {sum += cur2->val;cur2 = cur2->next;}cur->next = new ListNode(sum%10);cur = cur->next;sum /= 10;}ListNode* tmp = phead->next;delete phead;return tmp;}

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

题目要求：

解题思路：

思路：通过两个指针遍历链表，遍历的同时，将指针指向的节点按照顺序头插入新的节点中

实现代码：

    ListNode* swapPairs(ListNode* head) {if(head == nullptr || head->next == nullptr) {return head;}ListNode* prev = head, *cur = head->next;ListNode* phead = new ListNode(0);ListNode* tmp = phead;while(prev && cur) {tmp->next = new ListNode(cur->val);tmp = tmp->next;tmp->next = new ListNode(prev->val);tmp = tmp->next;prev = cur->next;if(prev) {cur = prev->next;}}tmp->next = prev;tmp = phead->next;delete phead;return tmp;}

三：重排链表

题目要求：

解题思路：

思路：

①通过快慢指针找到中间节点，此时慢指针将整个链表分成两段

②断开前一段，以及翻转后一段

③合并两个链表

实现代码：

ListNode * Reverse(ListNode * head) {ListNode* phead = nullptr;ListNode* cur = head;while (cur) {ListNode* next = cur->next;cur->next = phead;phead = cur;cur = next;}return phead;}//思路：找到中间节点并翻转，然后合并两个链表void reorderList(ListNode * head) {//排除边界条件if (head->next == nullptr || head->next->next == nullptr) {return;}//找中间节点ListNode* fast = head,* slow = head,* tmp = head;while (fast && fast->next) {fast = fast->next->next;tmp = slow;slow = slow->next;}//断开前一个链表tmp->next = nullptr;ListNode* cur1 = head;ListNode* cur2 = Reverse(slow);//翻转第二个链表ListNode* phead = new ListNode(0);ListNode* cur = phead;//合并两个链表while (cur1 || cur2) {if(cur1) {ListNode* next = cur1->next;cur->next = cur1;cur = cur1;cur1 = next;}if(cur2) {ListNode* next = cur2->next;cur->next = cur2;cur = cur2;cur2 = next;}}head = phead->next;;delete phead;}

四：合并K个升序链表

题目要求：

解题思路：

思路：借助优先级队列来辅助解题

①将vector中，链表的头节点建成小堆，此时堆顶数据为最小值

②取堆顶数据，并用变量cur记录，再出堆顶数据，此时cur为vector中，某一链表的头节点

③将cur链接到一个新的链表中，同时判断cur->next 节点是否为空，若不为空，将其插入堆中，重新建堆，保证堆顶始终是最小值，当堆为空时，表示已经遍历完所有链表此时循环结束。

实现代码：

    struct com {//vector中默认的排序不满足题目要求，所以得自己实现bool operator()(const ListNode* x1, const ListNode* x2) {return x1->val > x2->val;}};ListNode* mergeKLists(vector<ListNode*>& lists) {priority_queue<ListNode*,vector<ListNode*>,com> heap;//将vector中，每个链表的头节点建堆for(auto l : lists) {if(l) heap.push(l);}ListNode* phead = new ListNode(0);ListNode* cur = phead;while(!heap.empty()) {cur->next = heap.top();//堆顶元素其实就是一个节点，且该节点为最小值，赋值给curheap.pop();//出堆顶，避免重复cur = cur->next;if(cur->next) {//如果vector中 某个链表仍存在下一个节点，则插入进堆中，重新建堆，确保堆顶仍为最小节点heap.push(cur->next);}}return phead->next;}

五：K个一组翻转链表

题目要求：

解题思路：

思路：

①：遍历链表，统计一个有几个节点total，n = total / k 得到需要翻转n次

②：创建一个链表头phead，定义两个链表变量cur、prev，令 cur = head, prev = phead; 创建一个链表遍历 next = cur->next;如图所示：

③：通过两次循环，外循环为总共翻转的次数，内循环为每次翻转时，需要翻转的数的个数。在进行内循环前，定义一个链表遍历 tmp = cur，如图所示：

④：在内循环中，我们进行头插操作
for(int j = 0; j < k; j++) {ListNode* next = cur->next;cur->next = prev->next;prev->next = cur;cur = next;
{
当内循环一轮结束时，此时指针指向如图所示：

⑤：此时我们需将prev更新至tmp位置，以满足下一次循环能够进行头插操作，下一次内循环开始前，又会将tmo更新至cur位置，这样第二次循环结束时，同样将prev的位置更新至tmp，开始第三次头插，直至外循环结束。如图所示

⑥：当外循环结束时，此时判断cur是否为空，若不为空，则将后续数据链接到prev后面。

实现代码：

    ListNode* reverseKGroup(ListNode* head, int k) {if(head->next == nullptr) {return head;}ListNode* cur = head;int total = 0;while(cur) {total++;cur = cur->next;}int n = total / k;ListNode* phead = new ListNode(0);cur = head;ListNode *prev = phead;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;}if(cur) {prev->next = cur;}ListNode* ret =  phead->next;delete phead;return ret;}