逐日算法-链表（2.两数相加、24.两两交换链表中的节点、143.重排链表） ...

一.两数相加

1.1题目描述

1.2题解思绪

定义两个指针l1,l2依次遍历两个链表，用变量add存储l1加l2的值，将add的个位数取出来充当新节点的值，然后将add的个位数删去，即add /=10，循环此操作。
重点分析：
1.跟归并排序中合并两个有序数组类似，当两个链表并不是一样长，此中一个链表并没有遍历完！！！
2.当两个链表都遍历完之后，如果add的值为1，则必要再增加一个节点，它的值为1.
1.3.题解代码

1. class Solution {
2. public:
3.     ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
4.         int add = 0;
5.         ListNode* newhead = new ListNode(-1);//创建虚拟头结点
6.         ListNode* cur = newhead;
7.         while(l1 && l2)
8.         {
9.             add += l1->val + l2->val;
10.             ListNode* tmp = new ListNode(add%10);//将个位存进去
11.             add /= 10;
12.             cur->next = tmp;
13.             l1 = l1->next;
14.             l2 = l2->next;
15.             cur = cur->next;
16.         }
17.         while(l1)
18.         {
19.             add += l1->val;
20.             ListNode* tmp = new ListNode(add%10);
21.             add /= 10;
22.             cur->next = tmp;
23.             l1 = l1->next;
24.             cur = cur->next;
25.         }
26.         while(l2)
27.         {
28.             add += l2->val;
29.             ListNode* tmp = new ListNode(add%10);
30.             add /= 10;
31.             cur->next = tmp;
32.             l2 = l2->next;
33.             cur = cur->next;
34.         }
35.         //判断边界情况
36.         if(add == 1)
37.         {
38.             ListNode* tmp = new ListNode(1);
39.             cur->next = tmp;
40.             cur = cur->next;
41.         }
42.         return newhead->next;
43.     }
44. };

复制代码

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

2.1题目描述

2.2题解思绪

起首添加假造头结点，遍历这个链表，定义四个指针，prev,cur,next,nnext，模仿实现两个相邻链表翻转，然后更新prev,cur,next,nnext，循环此操作
重点分析：
1.当给的链表为空大概只有一个数据时，直接返回。
2.循环结束条件，当是偶数个数字时，cur!=nullptr，当是奇数个数字时，next != nullptr。
2.3题解代码

1. class Solution {
2. public:
3.     ListNode* swapPairs(ListNode* head) {
4.         if(!head || !head->next) return head;
5.         ListNode* newhead = new ListNode(-1);//虚拟头节点
6.         newhead->next = head;
7.         ListNode* prev = newhead,*cur = prev->next,*next = cur->next,*nnext = next->next;
8.         while(cur && next)
9.         {
10.             prev->next = next;
11.             next->next = cur;
12.             cur->next = nnext;
13.             prev = cur;
14.             cur = nnext;
15.             if(cur )next = cur->next;
16.             if(next) nnext = next->next;
17.         }
18.         return newhead->next;
19.     }
20. };

复制代码

三.重排链表

3.1题目描述

3.2题解思绪

1.找到链表的中央节点(快慢双指针)
2.将第二个链表逆序（头插法）
注意区分开curnext与cur->next，tmpnext与tmp->next

3.合并两个链表
注意必要把第一个链表的最后一个节点的next置空

3.3题解代码

1. class Solution {
2. public:
3.     void reorderList(ListNode* head) {
4.         if(!head->next || !head->next->next) return;        
5.         ListNode* newhead = new ListNode(-1);//添加虚拟头结点            
6.         //找到链表的中间节点(快慢双指针)   
7.         ListNode* q1 = head,*q2 = head;
8.         while( q2->next && q2->next->next)
9.         {
10.             q1 = q1->next;
11.             q2 = q2->next->next;
12.         }
13.         //反转q1后面的节点(头插法)
14.         ListNode* tmp = new ListNode(-2);
15.         ListNode* cur = q1->next,*curnext = cur->next,*tmpnext = tmp->next;
16.         while(cur)
17.         {
18.             cout<<cur->val;
19.             //头插
20.             tmp->next = cur;
21.             cur->next = tmpnext;
22.             //更新指针
23.             cur = curnext;
24.             if(cur) curnext = cur->next;
25.             tmpnext = tmp->next;
26.         }
28.         //合并两个链表
29.         q1->next = nullptr;//注意！！！
30.         ListNode* cur1 = head,*cur2 = tmp->next;
31.         cur = newhead;
32.         while(cur1 || cur2)
33.         {
34.             if(cur1)
35.             {
36.                 cur->next = cur1;
37.                 cur1 = cur1->next;
38.                 cur = cur->next;
39.                 cur->next = nullptr;
40.             }
41.             if(cur2)
42.             {
43.                 cur->next = cur2;
44.                 cur2 = cur2->next;
45.                 cur = cur->next;
46.                 cur->next = nullptr;
47.             }
48.         }
49.     }
50. };

复制代码

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