在這里積累這個題的目的是學習代碼的寫法，學習他人的代碼

這是自己的代碼：

class Solution 
{
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode* newhead = new ListNode();ListNode* cur1 = l1;ListNode* cur2 = l2;ListNode* cur = newhead;int carry = 0, sum = 0, ret = 0;while(cur1 && cur2){// 計算出這個節點要存的值是多少sum = cur1->val + cur2->val + carry;carry = sum / 10;ret = sum % 10;// 插入節點ListNode* newnode = new ListNode(ret);cur->next = newnode;cur = newnode;// 迭代cur1 = cur1->next;cur2 = cur2->next;}while(cur1){// 計算出這個節點要存的值是多少sum = cur1->val + carry;carry = sum / 10;ret = sum % 10;// 插入節點ListNode* newnode = new ListNode(ret);cur->next = newnode;cur = newnode;// 迭代cur1 = cur1->next;}while(cur2){// 計算出這個節點要存的值是多少sum = cur2->val + carry;carry = sum / 10;ret = sum % 10;// 插入節點ListNode* newnode = new ListNode(ret);cur->next = newnode;cur = newnode;// 迭代cur2 = cur2->next;}if(carry){// 插入節點ListNode* newnode = new ListNode(carry);cur->next = newnode;cur = newnode;}return newhead->next;}
};

運行可以通過，但是代碼量比較冗余，其實可以發現while循環和后面的if語句有相當多的相似語句，因此看下面的代碼：

class Solution 
{
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode* newhead = new ListNode();ListNode* cur1 = l1;ListNode* cur2 = l2;ListNode* cur = newhead;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;}// 處理掉不必要的內存空間cur = newhead->next;delete newhead;return cur;}
};

其實這個題已經見過很多次了，有很多種解決方法，直接模擬，遞歸…

但是這里積累它的意義在于，引入虛擬頭節點對于解題是很有幫助的

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution 
{
public:ListNode* swapPairs(ListNode* head) {if(head == nullptr || head->next == nullptr)return head;ListNode* newhead = new ListNode();newhead->next = head;ListNode* prev = newhead;ListNode* cur = newhead->next;ListNode* next = cur->next;ListNode* nnext = next->next;while(cur && next){// 交換節點prev->next = next;next->next = cur;cur->next = nnext;// 迭代prev = cur;cur = prev->next;if(cur) next = cur->next;if(next) nnext = next->next;}ListNode* res = newhead->next;delete newhead;return res;}
};

不帶虛擬頭節點：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution 
{
public:ListNode* swapPairs(ListNode* head) {if(head == nullptr || head->next == nullptr)return head;// 先找到新的頭節點ListNode* newhead = head->next;// 找到當前待交換的兩個節點ListNode* left = head;ListNode* right = head->next;while(left && right){// 交換兩個節點left->next = right->next;right->next = left;// 進行迭代ListNode* prev = left;left = left->next;if(left){right = left->next;if(right)prev->next = right;}}return newhead;}
};

遞歸解題

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution 
{
public:ListNode* swapPairs(ListNode* head) {if(head == nullptr || head->next == nullptr)return head;ListNode* left = head;ListNode* right = left->next;ListNode* tmp = right->next;right->next = left;left->next = swapPairs(tmp);return right;}
};

積累本題的意義在于，本題綜合了逆序鏈表，快慢指針，鏈表插入的問題，是一個綜合性的題

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution 
{
public:void reorderList(ListNode* head) {// 利用快慢雙指針找到中間節點ListNode* slow = head;ListNode* fast = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;}// 得到兩個新鏈表ListNode* newheadleft = head;ListNode* newheadright = Reverse(slow->next);slow->next = nullptr;// 把這兩個鏈表再組裝起來ListNode* newhead = new ListNode();ListNode* tail = newhead;ListNode* cur1 = newheadleft;ListNode* cur2 = newheadright;while(cur1 || cur2){if(cur1){tail->next = cur1;tail = tail->next;cur1 = cur1->next;}if(cur2){tail->next = cur2;tail = tail->next;cur2 = cur2->next;}}ListNode* res = newhead->next;delete newhead;head = res;}ListNode* Reverse(ListNode* head){ListNode* newhead = new ListNode();ListNode* cur = head;while(cur){ListNode* next = cur->next;cur->next = newhead->next;newhead->next = cur;cur = next;}ListNode* res = newhead->next;delete newhead;return res;}
};

關于這個題，乍一看其實是很難想到用什么方法做的，而實際上如果要是使用優先級隊列或者是遞歸的思想來解題是可以解決的，算法的思路難，但是實際的變現并不難

這里提供三種解題方法：暴力求解、利用優先級隊列來解題、利用歸并的思想來解題

暴力求解

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution 
{
public:// 利用合成的思想解題ListNode* mergeKLists(vector<ListNode*>& lists) {ListNode* newhead = new ListNode();ListNode* tail = newhead;for(int i = 0; i < lists.size(); i++){merge(newhead->next, lists[i]);}return newhead->next;}void merge(ListNode*& head, ListNode* cur){ListNode* newhead = new ListNode();ListNode* tail = newhead;while(head && cur){if(head->val < cur->val){tail->next = head;tail = tail->next;head = head->next;}else{tail->next = cur;tail = tail->next;cur = cur->next;}}if(head) tail->next = head;if(cur) tail->next = cur;head = newhead->next;}
};

利用優先級隊列的思想解題

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution 
{
public:struct cmp{bool operator()(ListNode* l1, ListNode* l2){return l1->val > l2->val;}};// 利用優先級隊列進行優化ListNode* mergeKLists(vector<ListNode*>& lists) {priority_queue<ListNode*, vector<ListNode*>, cmp> pq;// 把每一個鏈表都塞進去for(int i = 0; i <lists.size(); i++){if(lists[i])pq.push(lists[i]);}// 創建虛擬頭節點，開始鏈入到鏈表中ListNode* newhead = new ListNode();ListNode* tail = newhead;// 找到最小的節點，拿出來，再把它的下一個節點再塞進去，直到隊列為空while(!pq.empty()){ListNode* top = pq.top();pq.pop();if(top != nullptr){ListNode* next = top->next;top->next = nullptr;// 塞到目標鏈表中tail->next = top;tail = tail->next;// 再把剩下的部分再塞進去if(next)pq.push(next);}}// 返回信息ListNode* res = newhead->next;delete newhead;return res;}
};

利用歸并的思想解題

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution 
{
public:// 采用歸并的方式進行解題ListNode* mergeKLists(vector<ListNode*>& lists) {return merge(lists, 0, lists.size() - 1);}// 歸并排序ListNode* merge(vector<ListNode*>& lists, int left, int right){// 處理特殊情況if(left > right) return nullptr;if(left == right) return lists[left];// 拆分數組int midi = left + (right - left) / 2;// [left, midi][midi + 1, right]ListNode* l1 = merge(lists, left, midi);ListNode* l2 = merge(lists, midi + 1, right);// 排序return mergetwonode(l1, l2);}// 合并鏈表ListNode* mergetwonode(ListNode* l1, ListNode* l2){ListNode* newhead = new ListNode();ListNode* cur1 = l1, *cur2 = l2, *tail = newhead;while(cur1 && cur2){if(cur1->val <= cur2->val){tail->next = cur1;cur1 = cur1->next;tail = tail->next;}else{tail->next = cur2;cur2 = cur2->next;tail = tail->next;}}if(cur1) tail->next = cur1;if(cur2) tail->next = cur2;ListNode* res = newhead->next;delete newhead;return res;}
};

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution 
{// 思路：把鏈表k個一組拿出來，再翻轉，再鏈入一個新的鏈表中
public:ListNode* reverseKGroup(ListNode* head, int k) {ListNode* newhead = new ListNode();ListNode* tail = newhead;ListNode* left = head, *right = left;while(left && right){// 把鏈表k個一組分出來for(int i = 1; i < k; i++){// 如果此時已經到最后了，那么這最后一組就不需要進行翻轉if(right == nullptr){tail->next = left;return newhead->next;}right = right->next;}// 斷鏈if(right){ListNode* newleft = right->next;right->next = nullptr;// 現在從[left, right]就是一段完整的不帶頭節點的鏈表了// 把這段鏈表進行翻轉，并鏈入到新的鏈表中tail->next = reverse(left);tail = left;// 迭代，找下一組k個節點left = newleft, right = left;}}tail->next = left;return newhead->next;}// 進行鏈表的反轉ListNode* reverse(ListNode* cur){ListNode* newhead = new ListNode();// 把鏈表中的節點頭插到新鏈表中while(cur){ListNode* next = cur->next;cur->next = newhead->next;newhead->next = cur;cur = next;}ListNode* res = newhead->next;delete newhead;return res;}
};

這個題的難點在于細節問題的處理，其實思路并不難