一.兩數相加

1.1題目描述

1.2題解思路

定義兩個指針l1,l2依次遍歷兩個鏈表，用變量add存儲l1加l2的值，將add的個位數取出來充當新節點的值，然后將add的個位數刪去，即add /=10，循環此操作。

重點分析：

1.跟歸并排序中合并兩個有序數組類似，當兩個鏈表并不是一樣長，其中一個鏈表并沒有遍歷完！！！

2.當兩個鏈表都遍歷完之后，如果add的值為1，則需要再增加一個節點，它的值為1.

1.3.題解代碼

class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {int add = 0;ListNode* newhead = new ListNode(-1);//創建虛擬頭結點ListNode* cur = newhead;while(l1 && l2){add += l1->val + l2->val;ListNode* tmp = new ListNode(add%10);//將個位存進去add /= 10;cur->next = tmp;l1 = l1->next;l2 = l2->next; cur = cur->next;}while(l1){add += l1->val;ListNode* tmp = new ListNode(add%10);add /= 10;cur->next = tmp;l1 = l1->next;cur = cur->next;}while(l2){add += l2->val;ListNode* tmp = new ListNode(add%10);add /= 10;cur->next = tmp;l2 = l2->next; cur = cur->next;}//判斷邊界情況if(add == 1){ListNode* tmp = new ListNode(1);cur->next = tmp;cur = cur->next;}return newhead->next;}
};

二.兩兩交換鏈表中的節點

2.1題目描述

2.2題解思路

首先添加虛擬頭結點，遍歷這個鏈表，定義四個指針，prev,cur,next,nnext，模擬實現兩個相鄰鏈表翻轉，然后更新prev,cur,next,nnext，循環此操作

重點分析：

1.當給的鏈表為空或者只有一個數據時，直接返回。

2.循環結束條件，當是偶數個數字時，cur!=nullptr，當是奇數個數字時，next != nullptr。

2.3題解代碼

class Solution {
public:ListNode* swapPairs(ListNode* head) {if(!head || !head->next) return head;ListNode* newhead = new ListNode(-1);//虛擬頭節點newhead->next = head;ListNode* prev = newhead,*cur = prev->next,*next = cur->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;}return newhead->next;}
};

三.重排鏈表

3.1題目描述

3.2題解思路

1.找到鏈表的中間節點(快慢雙指針)

2.將第二個鏈表逆序（頭插法）

注意區分開curnext與cur->next，tmpnext與tmp->next

3.合并兩個鏈表

注意需要把第一個鏈表的最后一個節點的next置空

3.3題解代碼

class Solution {
public:void reorderList(ListNode* head) {if(!head->next || !head->next->next) return;        ListNode* newhead = new ListNode(-1);//添加虛擬頭結點            //找到鏈表的中間節點(快慢雙指針)    ListNode* q1 = head,*q2 = head;while( q2->next && q2->next->next){q1 = q1->next;q2 = q2->next->next;}//反轉q1后面的節點(頭插法)ListNode* tmp = new ListNode(-2);ListNode* cur = q1->next,*curnext = cur->next,*tmpnext = tmp->next;while(cur){cout<<cur->val;//頭插tmp->next = cur;cur->next = tmpnext;//更新指針cur = curnext;if(cur) curnext = cur->next;tmpnext = tmp->next;}//合并兩個鏈表q1->next = nullptr;//注意！！！ListNode* cur1 = head,*cur2 = tmp->next;cur = newhead;while(cur1 || cur2){if(cur1){cur->next = cur1;cur1 = cur1->next;cur = cur->next;cur->next = nullptr;}if(cur2){cur->next = cur2;cur2 = cur2->next;cur = cur->next;cur->next = nullptr;}}}
};