算法笔记（六）——链表

技巧:
  

• 画图观察指针指向；
  
• 添加虚拟头节点；
  
• 可以多界说几个节点；
  
• 快慢双指针；
  

    常见操作：
  

• 界说new head
  
• 逆序时，头插
  

1. ListNode* newhead = new ListNode(0);
2. ListNode* cur= head;
3. ListNode* next = cur->next;
4. cur->next = head->next;
5. head->next = cur;
6. cur = next

复制代码

两数相加

   题目：两数相加
  

思路
   逆序的链表，只需要一个临时变量来记录进位的值，然后我们可以正常按照计算规则逐个相加直至链表竣事
  C++代码

1. /**
2. * Definition for singly-linked list.
3. * struct ListNode {
4. *     int val;
5. *     ListNode *next;
6. *     ListNode() : val(0), next(nullptr) {}
7. *     ListNode(int x) : val(x), next(nullptr) {}
8. *     ListNode(int x, ListNode *next) : val(x), next(next) {}
9. * };
10. */
11. class Solution
12. {
13. public:
14.     ListNode* addTwoNumbers(ListNode* l1, ListNode* l2)
15.     {
16.         ListNode* newhead = new ListNode(-1);
17.         ListNode* prev = newhead;
18.         ListNode* cur1 = l1;
19.         ListNode* cur2 = l2;
21.         int t = 0;
23.         while(cur1 || cur2 || t)
24.         {
25.             if(cur1)
26.             {
27.                 t += cur1->val;
28.                 cur1 = cur1->next;
29.             }
30.             if(cur2)
31.             {
32.                 t += cur2->val;
33.                 cur2 = cur2->next;
34.             }
36.             prev->next = new ListNode(t % 10);
37.             prev = prev->next;
38.             t /= 10;
39.         }
41.         prev = newhead->next;
42.         delete newhead;
43.    
44.         return prev;
45.     }
46. };

复制代码

两两交换链表中的节点

   题目：两两交换链表中的节点
  

思路

循环停止条件

• 奇节点数，next == NUL
  
• 偶节点数，cur == NULL
  

C++代码

1. /**
2. * Definition for singly-linked list.
3. * struct ListNode {
4. *     int val;
5. *     ListNode *next;
6. *     ListNode() : val(0), next(nullptr) {}
7. *     ListNode(int x) : val(x), next(nullptr) {}
8. *     ListNode(int x, ListNode *next) : val(x), next(next) {}
9. * };
10. */
11. class Solution
12. {
13. public:
14.     ListNode* swapPairs(ListNode* head)
15.     {
16.         if(head == nullptr || head->next == nullptr)
17.             return head;
19.         ListNode* newhead=new ListNode();
20.         newhead->next = head;
22.         ListNode* prev = newhead;
23.         ListNode* cur = prev->next, *next = cur->next, *nnext = next->next;
25.         while(cur && next)
26.         {
27.             // 重新连接节点(顺序无所谓)
28.             prev->next = next;
29.             next->next = cur;
30.             cur->next = nnext;
32.             // 迭代节点(注意顺序)
33.             prev = cur;
34.             cur = nnext;
35.             if(cur) next = cur->next;
36.             if(next) nnext = next->next;
37.         }
38.         prev=newhead->next;
39.         delete newhead;
40.         return prev;
41.     }
42. };

复制代码

重排链表

   题目：重排链表
  

思路

• 模仿
  
• 
  
  • 找到链表的中心节点； 快慢双指针
    
  
  
• 
  
  • 逆序后面的链表；头插
    
  
  
• 
  
  • 归并两个链表；双指针
    
  
  

C++代码

1. /**
2. * Definition for singly-linked list.
3. * struct ListNode {
4. *     int val;
5. *     ListNode *next;
6. *     ListNode() : val(0), next(nullptr) {}
7. *     ListNode(int x) : val(x), next(nullptr) {}
8. *     ListNode(int x, ListNode *next) : val(x), next(next) {}
9. * };
10. */
11. /**
12. * Definition for singly-linked list.
13. * struct ListNode {
14. *     int val;
15. *     ListNode *next;
16. *     ListNode() : val(0), next(nullptr) {}
17. *     ListNode(int x) : val(x), next(nullptr) {}
18. *     ListNode(int x, ListNode *next) : val(x), next(next) {}
19. * };
20. */
21. class Solution
22. {
23. public:
24.     void reorderList(ListNode* head)
25.     {
27.         ListNode* slow = head;
28.         ListNode* fast = head->next;
29.         while (fast && fast->next)
30.         {
31.             slow = slow->next;
32.             fast = fast->next->next;
33.         }
35.         //反转后半段链表
36.         ListNode* second = reverseList(slow->next);
37.         slow->next = nullptr;
38.         ListNode* first = head;
40.         //交替合并first和second
41.         while (second)
42.         {
43.             ListNode* tmpNode1 = first->next;
44.             ListNode* tmpNode2 = second->next;
45.             first->next = second;
46.             second->next = tmpNode1;
47.             first = tmpNode1;
48.             second = tmpNode2;
49.         }
50.     }
52.      ListNode* reverseList(ListNode* head)
53.      {
55.         if (head == nullptr) return head;
56.         
57.         ListNode* prev = nullptr;
58.         ListNode* cur = head;
59.         while (cur)
60.         {
61.             ListNode* tmp = cur->next;
62.             cur->next = prev;
63.             prev = cur;
64.             cur = tmp;
65.         }
67.         return prev;
68.     }
69. };

复制代码

归并 K 个升序链表

   题目：归并 K 个升序链表
  

思路

• 将每个链表的头节点入小堆，每次从堆顶元素开始链接，逐个将堆顶的最小链表节点链接，并不断向堆中添加后续元素；
  

C++代码

1. /**
2. * Definition for singly-linked list.
3. * struct ListNode {
4. *     int val;
5. *     ListNode *next;
6. *     ListNode() : val(0), next(nullptr) {}
7. *     ListNode(int x) : val(x), next(nullptr) {}
8. *     ListNode(int x, ListNode *next) : val(x), next(next) {}
9. * };
10. */
11. class Solution
12. {
13. public:
14.     struct cmp
15.     {
16.         bool operator()(const ListNode* l1,const ListNode* l2)
17.         {
18.             return l1->val > l2->val;
19.         }
20.     };
21.     ListNode* mergeKLists(vector<ListNode*>& lists)
22.     {   
23.         // 小堆
24.         priority_queue<ListNode*,vector<ListNode*>, cmp> heap;
26.         // 所有头节点进堆
27.         for(auto l : lists)
28.             if(l) heap.push(l);
30.         // 合并
31.         ListNode* ret = new ListNode(0);
32.         ListNode* prev = ret;
34.         while(!heap.empty())
35.         {
36.             ListNode* t = heap.top();
37.             heap.pop();
38.             prev->next = t;  
39.             prev = t;
40.             if(t->next != nullptr) heap.push(t->next);
42.         }
44.         prev = ret->next;
45.         delete ret;
46.         return prev;
47.     }
48. };

复制代码

K个一组翻转链表

   题目：K 个一组翻转链表
  

思路

• 计算需要翻转的次数
  
• 重复 n 次，长度为 k 的链表的逆序
  

C++代码

1. /**
2. * Definition for singly-linked list.
3. * struct ListNode {
4. *     int val;
5. *     ListNode *next;
6. *     ListNode() : val(0), next(nullptr) {}
7. *     ListNode(int x) : val(x), next(nullptr) {}
8. *     ListNode(int x, ListNode *next) : val(x), next(next) {}
9. * };
10. */
11. class Solution
12. {
13. public:
14.     ListNode* reverseKGroup(ListNode* head, int k)
15.     {
16.         // 统计节点个数
17.         int n = 0;
18.         ListNode* cur = head;
19.         while(cur)
20.         {
21.             n++;
22.             cur = cur->next;
23.         }
24.         n /= k;
26.         // 重复n次长度为k的链表逆序
27.         ListNode* newhead = new ListNode(0);
28.         ListNode* prev = newhead;
29.         cur = head;
30.         for(int i = 0; i < n; i++)
31.         {
32.             ListNode* tmp = cur;
33.             for(int j = 0; j < k; j++)
34.             {
35.                 ListNode* next = cur->next;
36.                 cur->next = prev->next;
37.                 prev->next = cur;
38.                 cur = next;
39.             }
40.             prev = tmp;
41.         }
42.         prev->next = cur;
44.         return newhead->next;
45.     }
46. };

复制代码

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