題目描述：

思路講解：
本道題只需要模擬兩數相加的過程即可，首先定義一個虛擬頭結點，這樣就不需要對鏈表進行特殊處理，然后定義兩個變量分別記錄對應位上兩數相加的個位和進位，創建一個節點存儲個位上的數字，尾插到虛擬頭結點所在的鏈表中，然后同時將兩個原始鏈表向后同時移動，重復上面的操作，直到兩個鏈表都遍歷完后返回以虛擬頭結點后面一個節點為頭結點的鏈表即完成本題。

需要注意兩數相加時還要加上進位，若是某個鏈表對應位上沒有節點，我們認定這個節點上的數字為0。

編寫代碼：

/*** 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* addTwoNumbers(ListNode* l1, ListNode* l2) {int add = 0;ListNode* newhead = new ListNode();ListNode* cur = newhead;while(l1 || l2 || add){int num1 = (l1 != nullptr) ? l1->val : 0;int num2 = (l2 != nullptr) ? l2->val : 0;int sum = num1 + num2 + add;ListNode* newNode = new ListNode(sum % 10);cur->next = newNode;cur = cur->next;add = sum / 10;if(l1 != nullptr)   l1 = l1->next;if(l2 != nullptr)   l2 = l2->next;}return newhead->next;}
};

題目描述：

思路講解：
本道題我們需要做的就是將鏈表中每兩個節點進行交互即可，我們只需要模擬如何將節點進行交換即可。若鏈表中只有一個節點時，不需要進行交換，返回即可。

這里我創建一個虛擬頭結點用來避免對鏈表第一次交換進行特殊處理，通過畫圖我們發現，看似是對兩個節點進行交換，實際上卻涉及到了四個節點，為了我們方便處理，直接定義四個指針分別指向四個連續的節點，有了這四個指針就可以很方便的將兩個節點進行交換了，如下圖，我們只需要修改prve、cur和next指向節點中next的指向即可，修改完指向后就需要指針向后移動了，各個指針移動后對應的位置在下圖中有明確的標識，有些指針移動后位置比較特殊，需要特殊判斷。

然后就是循環的判斷條件了，這里我們將鏈表分類奇數節點個數和偶數節點個數來看，如圖，奇數情況下只要next沒有指向節點就結束，偶數情況下cur沒有指向節點就結束，綜上只要cur或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:ListNode* swapPairs(ListNode* head) {if(head == nullptr || head ->next == nullptr)return head;ListNode* newhead = new ListNode();ListNode* prev = newhead ,*cur = head ;ListNode* next = head->next , *nnext = next->next;while(cur != nullptr && next != nullptr){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;}
};

題目描述：

思路講解：

本道題是讓我們將鏈表重新排序，并且不能只修改節點的值，而是要進行節點之間的切換，我們看了題目的示例，可以得出重排鏈表，實際上是重復拿出原鏈表中的頭節點和尾節點，并將尾節點鏈接到頭節點的后面，然后按照拿出來的順序進行鏈接，即可完成對鏈表的重排。

本題還有一個更簡單的思路，就是將這個鏈表從中間分開變為兩個鏈表，使前面鏈表的節點個數比后面的鏈接節點個數多一個或是相等，然后將后面這個鏈表逆轉，最后通過兩個鏈表的合并即可完成鏈表的重排。

編寫代碼：

/*** 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) {if(head->next == nullptr)return;ListNode* slow = head , *fast = head -> next;while(fast && fast->next){slow = slow->next;fast = fast->next->next;}// 從中間截斷為兩段鏈表ListNode* newhead1 = new ListNode();ListNode* cur = slow -> next;slow->next = nullptr;ListNode* next = cur->next;// 逆置后半段鏈表cur->next = nullptr;while(cur){cur->next = newhead1->next;newhead1 -> next = cur;cur = next;if(next)next = next -> next;}ListNode* cur1 = head ,*cur2 = newhead1->next;ListNode* next1 = head->next ,*next2 = cur2->next;ListNode* newhead2 = new ListNode();cur = newhead2;while(cur2){// 依次插入兩個鏈表cur -> next = cur1;cur1 = next1;if(next1)next1 = next1->next;cur = cur -> next;cur -> next = cur2;cur2 = next2;if(next2)next2 = next2->next;cur = cur -> next;}// 第一段鏈表一定與第二段鏈表等長或更長if(cur1)cur->next = cur1;head = newhead2;}
};

題目描述：

思路講解：
本道題是想讓我們將k個升序鏈表，按照節點的大小合并為1個升序鏈表，這里我們一定能想到的就是暴力解法，每次遍歷所以鏈表的頭節點，找到最小的節點并取出，再將這個節點鏈入到新鏈表中，重復這樣的操作，直到k個鏈表中沒有任何節點位置，最后返回新鏈表即可完成本道題，這樣完成本道題的時間復雜度為O(nk${}^2$)。

這里可以使用優先級隊列進行優化，我們創建一個小堆，將所有鏈表的頭節點放入小堆中，小堆根據節點的大小將最小的節點移動到堆頂，這樣我們就可以通過找到堆頂元素就可以找到k個鏈表中頭節點中最小的節點了，將該節點從堆中和它所對應的鏈表中取出，并將它所對應鏈表中的新頭節點放入到堆中，若沒有節點則不需加入，小堆則會按照它的特性將堆中的節點重新調整，然后將取出來的節點鏈接到新的鏈表中，重復這樣的操作直到堆中沒有任何節點為止，最后將新鏈表返回即可完成合并 K 個升序鏈表。

編寫代碼：

/*** 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) {int count = lists.size(); // 鏈表的個數ListNode* newhead = new ListNode();ListNode* last = newhead;// 記錄鏈表中有節點的鏈表個數int ListCount = 0;while(1){int MinPos = 0;int min = 10001;for(int i = 0 ; i < count; i++){ListNode* cur = lists[i];if(cur){   ListCount++;if(min > cur->val){min = cur->val;MinPos = i;}}}// 當鏈表所有鏈表都沒有節點時跳出循環if(ListCount == 0)break;last->next = lists[MinPos];// 插入到新的鏈表中last = last -> next;if(lists[MinPos])lists[MinPos] = lists[MinPos]->next;MinPos = 0 , ListCount = 0;}return newhead->next;}
};

題目描述：

思路講解：
本道題想讓我們將鏈表中每k個節點進行翻轉，若剩下的節點小于k個則保持愿意。

這里可以使用模擬的思路解決本題，我們先遍歷整個鏈表，得到鏈表中節點的個數為num，有每k個節點需要翻轉一次，通過num/k得到有count組子鏈表需要翻轉。循環count次，每次記錄該組子鏈表的前一個節點和后一個節點，將本組k個節點進行逆序，再鏈接回原鏈表中，這里可以使用頭插法的方式將鏈表進行逆序，最后返回鏈表的頭結點即可。

編寫代碼：

/*** 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* reverseKGroup(ListNode* head, int k) {int numNode = 0;  // 節點個數ListNode* cur = head;while(cur){numNode++;cur = cur->next;}int opCount = numNode / k;  // 記錄需要翻轉的次數ListNode* newhead = new ListNode();   // 創建哨兵位頭結點newhead->next = head;ListNode* prev = newhead; // 標記每k個節點的前一個節點，方便鏈接cur = head;ListNode* connect = cur; // 旋轉k個節點后的最后一個節點，方便鏈接ListNode* next = cur->next; while(opCount--){connect = cur;for(int i = 1 ; i <= k ; i++){cur->next = prev->next;prev->next = cur;cur = next;if(next)next = next->next;}// 記錄前一段的尾prev = connect;}prev->next = cur;return newhead->next;}
};