---

0.常用技巧

• 画图 -> 直观 + 形象 -> 便于理解

• 引入虚拟头结点

  • 便于处理边界情况
  • 方便对链表操作

• 不要吝啬空间，大胆去定义变量

  • 简化插入删除的逻辑
  • 都是函数内的临时变量，也不会很占用空间:P
    

• 快慢双指针

  • 判环
  • 找链表中环的入口
  • 找链表中倒数第n个结点

---

1.两数相加

1.题目链接

• 两数相加

---

2.算法原理详解

• 两个链表都是逆序存储数字的
  • 即：两个链表的个位数、⼗位数等都已经对应，可以直接相加
• 在相加过程中，要注意是否产⽣进位，产⽣进位时需要将进位和链表数字⼀同相加
  • 如果产⽣进位的位置在链表尾部，即答案位数⽐原链表位数⻓⼀位，还需要再new⼀个结点储存最⾼位

---

3.代码实现

ListNode* AddTwoNumbers(ListNode* l1, ListNode* l2) 
{ListNode* head = new ListNode(0);ListNode* cur1 = l1, *cur2 = l2;ListNode* tail = head; // 尾指针int carry = 0; // 记录进位 & 临时数据while(cur1 || cur2 || carry){if(cur1){carry += cur1->val;cur1 = cur1->next;}if(cur2){carry += cur2->val;cur2 = cur2->next;}tail->next = new ListNode(carry % 10);tail = tail->next;carry /= 10;}ListNode* ret = head->next;delete head;return ret;
}

---

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

1.题目链接

• 两两交换链表中的节点

---

2.算法原理详解

---

3.代码实现

ListNode* SwapPairs(ListNode* list) 
{// 边界处理if(list == nullptr || list->next == nullptr){return list;}ListNode *head = new ListNode(0);head->next = list;ListNode *prev = head, *cur = head->next, *next = cur->next, *nNext = next->next;while(cur && next){// Swapprev->next = next;next->next = cur;cur->next = nNext;// Updateprev = cur;cur = nNext; if(cur){next = cur->next;}if(next){nNext = next->next;}}ListNode *ret = head->next;delete head;return ret;
}

---

3.重排链表

1.题目链接

• 重排链表

---

2.算法原理详解

• 找到链表的中间结点
  • 快慢双指针
• 把后面部分逆序
  • 头插法
• 合并两个链表
  • 双指针
    

---

3.代码实现

void ReorderList(ListNode* head) 
{// 边界处理if(!(head || head->next || head->next->next)){return;}// 1.找到链表的中间结点 -> 快慢指针ListNode *slow = head, *fast = head;while(fast && fast->next) // 偶 && 奇{slow = slow->next;fast = fast->next->next;}// 2.逆序后半部分 -> 头插ListNode *head2 = new ListNode(0);ListNode *cur = slow->next;slow->next = nullptr; // 断开两个链表while(cur){ListNode *next = cur->next;cur->next = head2->next;head2->next = cur;cur = next;}// 3.合并两个链表 -> 尾插 -> 双指针ListNode *ret = new ListNode(0);ListNode *tail = ret;ListNode *cur1 = head, *cur2 = head2->next;while(cur1){// 先连第一个链表tail->next = cur1;tail = tail->next;cur1 = cur1->next;// 再连第二个链表if(cur2){tail->next = cur2;tail = tail->next;cur2 = cur2->next;}}delete head2;delete ret;
}

---

4.合并 K 个升序链表

1.题目链接

• 合并 K 个升序链表

---

2.算法原理详解

• 思路一：利用堆
  • 合并K个升序链表时，可以选择K个链表中，头结点值最⼩的那⼀个
  • 那么如何快速的得到头结点最⼩的是哪⼀个呢？
    • 小根堆
  • 可以把所有的头结点放进⼀个⼩根堆中，这样就能快速的找到每次K个链表中，最⼩的元素是哪个
• 思路二：递归/分治
  

---

3.代码实现

// v1.0 Heap
class Solution 
{struct Cmp{bool operator()(const ListNode* l1, const ListNode* l2){return l1->val > l2->val;}};
public:ListNode* mergeKLists(vector<ListNode*>& lists) {// 创建一个小根堆priority_queue<ListNode*, vector<ListNode*>, Cmp> heap;// 让所有头结点入堆for(auto& list : lists){if(list){heap.push(list);}}// 合并K个有序链表ListNode* ret = new ListNode(0);ListNode* tail = ret;while(!heap.empty()){ListNode* tmp = heap.top();heap.pop();tail->next = tmp;tail = tail->next;if(tmp->next){heap.push(tmp->next);}}tail = ret->next;delete ret;return tail;}
};// v2.0 递归
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 mid = left + (right - left) / 2;// [left, mid] [mid + 1, right]// 递归处理左右区间ListNode* l1 = Merge(lists, left, mid);ListNode* l2 = Merge(lists, mid + 1, right);// 合并两个有序链表return MergeTwoLists(l1, l2);}ListNode* MergeTwoLists(ListNode* l1, ListNode* l2){// 边界情况处理if(l1 == nullptr){return l2;}if(l2 == nullptr){return l1;}// 合并两有序链表ListNode head(0);ListNode *cur1 = l1, *cur2 = l2, *tail = &head;while(cur1 && cur2){if(cur1->val <= cur2->val){tail->next = cur1;tail = tail->next;cur1 = cur1->next;}else{tail->next = cur2;tail = tail->next;cur2 = cur2->next;}}if(cur1){tail->next = cur1;}if(cur2){tail->next = cur2;}return head.next;}
};

---

5.K 个一组翻转链表

1.题目链接

• K 个一组翻转链表

---

2.算法原理详解

• 思路：
  • 按k个一组，分出需要逆序多少组
    • 遍历链表求出n
    • n /= 3
  • 重复n次，长度为k的链表逆序即可

---

3.代码实现

ListNode* ReverseKGroup(ListNode* head, int k) 
{// 遍历求nint n = 0;ListNode* cur = head;while(cur){n++;cur = cur->next;}n /= k;// 重复n次逆序长度为k的链表 -> 头插ListNode ret(0);ListNode *prev = &ret;cur = head;while(n--){ListNode *back = cur;for(int i = 0; i < k; i++){ListNode* next = cur->next;cur->next = prev->next;prev->next = cur;cur = next;}prev = back; // 更次每次头插的"头"}// 链接剩下的结点prev->next = cur;return ret.next;
}