算法练习——链表

一：两数相加

题目要求：

解题思路：

   思路：注意进位即可
  实今世码：

1.     ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
2.         ListNode* cur1 = l1, * cur2 = l2;
3.         ListNode* phead = new ListNode(0);
4.         ListNode* cur = phead;
5.         int sum = 0;
6.         while(cur1 || cur2 || sum) {//除了两个链表中的数外，还要考虑进位，只要存在进位就要加
7.             if(cur1) {
8.                 sum += cur1->val;
9.                 cur1 = cur1->next;
10.             }
11.             if(cur2) {
12.                 sum += cur2->val;
13.                 cur2 = cur2->next;
14.             }
15.             cur->next = new ListNode(sum%10);
16.             cur = cur->next;
17.             sum /= 10;
18.         }
19.         ListNode* tmp = phead->next;
20.         delete phead;
21.         return tmp;
22.     }

复制代码

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

题目要求：

解题思路：

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

1.     ListNode* swapPairs(ListNode* head) {
2.         if(head == nullptr || head->next == nullptr) {
3.             return head;
4.         }
5.         ListNode* prev = head, *cur = head->next;
6.         ListNode* phead = new ListNode(0);
7.         ListNode* tmp = phead;
9.         while(prev && cur) {
10.             tmp->next = new ListNode(cur->val);
11.             tmp = tmp->next;
13.             tmp->next = new ListNode(prev->val);
14.             tmp = tmp->next;
15.             
16.             prev = cur->next;
17.             if(prev) {
18.                 cur = prev->next;
19.             }
20.         }
21.         tmp->next = prev;
22.         tmp = phead->next;
23.         delete phead;
24.         return tmp;
25.     }

复制代码

三：重排链表

题目要求：

解题思路：

   思路：
  ①通过快慢指针找到中心节点，此时慢指针将整个链表分成两段
  ②断开前一段，以及翻转后一段
  ③归并两个链表
  实今世码：

1. ListNode * Reverse(ListNode * head) {
2.         ListNode* phead = nullptr;
3.         ListNode* cur = head;
4.         while (cur) {
5.                         ListNode* next = cur->next;
6.             cur->next = phead;
7.             phead = cur;
8.             cur = next;
9.                 }
10.         return phead;
11.         }
13.         //思路：找到中间节点并翻转，然后合并两个链表
14.         void reorderList(ListNode * head) {
15.                 //排除边界条件
16.                 if (head->next == nullptr || head->next->next == nullptr) {
17.                         return;
18.                 }
19.                 //找中间节点
20.                 ListNode* fast = head,* slow = head,* tmp = head;
21.                 while (fast && fast->next) {
22.                         fast = fast->next->next;
23.             tmp = slow;
24.                         slow = slow->next;
25.                 }
26.                 //断开前一个链表
27.                 tmp->next = nullptr;
29.                 ListNode* cur1 = head;
30.                 ListNode* cur2 = Reverse(slow);//翻转第二个链表
31.                 ListNode* phead = new ListNode(0);
32.                 ListNode* cur = phead;
33.                 //合并两个链表
34.                 while (cur1 || cur2) {
35.             if(cur1) {
36.                 ListNode* next = cur1->next;
37.                 cur->next = cur1;
38.                 cur = cur1;
39.                 cur1 = next;
40.             }
41.             if(cur2) {
42.                 ListNode* next = cur2->next;
43.                 cur->next = cur2;
44.                 cur = cur2;
45.                 cur2 = next;
46.             }
47.                 }
48.                 head = phead->next;;
49.                 delete phead;
50.         }

复制代码

四：归并K个升序链表

题目要求：

解题思路：

   思路：借助优先级队列来辅助解题
  ①将vector中，链表的头节点建成小堆，此时堆顶数据为最小值
  ②取堆顶数据，并用变量cur记录，再出堆顶数据，此时cur为vector中，某一链表的头节点
  ③将cur链接到一个新的链表中，同时判断cur->next 节点是否为空，若不为空，将其插入堆中，重新建堆，包管堆顶始终是最小值，当堆为空时，表现已经遍历完全部链表此时循环竣事。
  实今世码：

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

复制代码

五：K个一组翻转链表

题目要求：

解题思路：

   思路：
  ①：遍历链表，统计一个有几个节点total，n = total / k 得到需要翻转n次
  ②：创建一个链表头phead，定义两个链表变量cur、prev，令 cur = head, prev = phead; 创建一个链表遍历 next = cur->next;如图所示：
  

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

  ④：在内循环中，我们进行头插操作

1. for(int j = 0; j < k; j++) {
2.     ListNode* next = cur->next;
3.     cur->next = prev->next;
4.     prev->next = cur;
5.     cur = next;
6. {

复制代码

当内循环一轮竣事时，此时指针指向如图所示：
  

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

  ⑥：当外循环竣事时，此时判断cur是否为空，若不为空，则将后续数据链接到prev反面。
  实今世码：

1.     ListNode* reverseKGroup(ListNode* head, int k) {
2.         if(head->next == nullptr) {
3.             return head;
4.         }
5.         ListNode* cur = head;
6.         int total = 0;
7.         while(cur) {
8.             total++;
9.             cur = cur->next;
10.         }
11.         int n = total / k;
12.         
13.         ListNode* phead = new ListNode(0);
14.         cur = head;
15.         ListNode *prev = phead;
16.         
17.         for(int i = 0; i < n; i++) {
18.             ListNode* tmp = cur;
19.             for(int j = 0; j < k; j++) {
20.                 ListNode* next = cur->next;
21.                 cur->next = prev->next;
22.                 prev->next = cur;
23.                 cur = next;
24.             }
25.             prev = tmp;
26.         }
27.         if(cur) {
28.             prev->next = cur;
29.         }
30.         ListNode* ret =  phead->next;
31.         delete phead;
32.         return ret;
33.     }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。