【链表世界的深度探索：从基础到高阶的算法解读】—— LeetCode

这道题目的意思很好理解，即将链表给反转即可

• 方法一：
  利用双指针进行操作，定义两个变量 prev 以及 curr 在遍历链表时，将当前节点curr 的next指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。

class Solution 
{
public:ListNode* reverseList(ListNode* head) {// 'prev' 用来跟踪前一个节点，初始化为 nullptrListNode* prev = nullptr;// 'curr' 用来跟踪当前节点，初始化为链表的头节点ListNode* curr = head;// 遍历链表直到到达末尾while (curr) {// 'next' 暂时保存当前节点的下一个节点ListNode* next = curr->next;// 将当前节点的 'next' 指针反转，指向前一个节点curr->next = prev;// 将 'prev' 移动到当前节点，成为下次循环中的前一个节点prev = curr;// 将 'curr' 移动到下一个节点curr = next;}// 循环结束后，'prev' 会指向反转后的链表的新头节点return prev;}
};

• 方法二：
  利用递归解决，从方法一当中可以知道，我们在while循环里面都是在做一件事情，所以通过递归解决。

class Solution 
{
public:ListNode* reverseList(ListNode* head) {// 如果链表为空或者只有一个节点，直接返回头节点if (!head || !head->next)return head;// 递归调用，反转后续的链表ListNode* newhead = reverseList(head->next);// 将当前节点（head）接到反转链表的后面head->next->next = head;// 断开当前节点（head）的 'next' 指针，避免形成循环head->next = nullptr;// 返回新的头节点return newhead;}
};

不知道大家看到这题的第一个想法是什么？当时我想到的是，在一条马路上，一个人走两步步频，一个人走一步步频，那么当走两步那个人到达终点的时候，走一步的那个人就是在终点了

• 方法一： 所以这题就可以通过快慢指针进行操作

class Solution 
{
public:ListNode* middleNode(ListNode* head) {// 'slow' 和 'fast' 都初始化为链表的头节点ListNode *slow = head, *fast = head;// 使用快慢指针法，'slow' 每次走一步，'fast' 每次走两步while (fast && fast->next){slow = slow->next;        // 慢指针每次移动一步fast = fast->next->next;  // 快指针每次移动两步}// 当 'fast' 到达链表的末尾时，'slow' 将指向链表的中间节点return slow;}
};

• 方法二：统计有多少个结点，然后除以二，就是那个结点的位置。

class Solution 
{
public:ListNode* middleNode(ListNode* head) {ListNode* p = head;int count = 0;// 如果链表为空，直接返回 nullptrif (head == nullptr)return nullptr;// 遍历链表，统计节点数while (p) {p = p->next;count++;}// 从头节点重新开始，找到中间节点p = head;for (int i = 0; i < count / 2; i++) {if (p == nullptr)return head;p = p->next;}// 返回中间节点return p;}
};

• 方法一：这题也是利用双指针进行解题，创建两个变量l1 l2分别指向两个链表的头，在一个while循环里面判断值的大小，值小的即插入到新创建的一个头结点当中，当l1 && l2有一个为空即停止，然后处理剩余最后的结点即可

class Solution 
{
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {// 如果其中一个链表为空，直接返回另一个链表if (list1 == nullptr)return list2;if (list2 == nullptr)return list1;// 创建一个新的头节点用于合并结果ListNode *newhead = new ListNode();ListNode *newtail = newhead;// 使用两个指针分别遍历两个链表ListNode *l1 = list1;ListNode *l2 = list2;// 合并两个链表while (l1 && l2) {if (l1->val < l2->val) {newtail->next = l1;newtail = newtail->next;l1 = l1->next;} else {newtail->next = l2;newtail = newtail->next;l2 = l2->next;}}// 处理剩余的节点（如果有的话）if (l1) {newtail->next = l1;}if (l2) {newtail->next = l2;}// 返回合并后的链表ListNode* ret = newhead->next;delete newhead; // 释放内存return ret;}
};

• 方法二：使用递归，来进行函数当中，具有重复性的事情

/*** 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* mergeTwoLists(ListNode* l1, ListNode* l2) {// 如果第一个链表为空，返回第二个链表if (l1 == nullptr) return l2;// 如果第二个链表为空，返回第一个链表if (l2 == nullptr) return l1;// 比较两个链表的头节点值，递归合并剩余部分if (l1->val <= l2->val){// 如果 l1 的值小于等于 l2，则将 l1 的下一个节点合并到 l2l1->next = mergeTwoLists(l1->next, l2);return l1;  // 返回 l1 作为新的合并后的链表头}else{// 如果 l2 的值小于 l1，则将 l2 的下一个节点合并到 l1l2->next = mergeTwoLists(l1, l2->next);return l2;  // 返回 l2 作为新的合并后的链表头}}
};

• 解法：简答题，直接两个变量分别遍历两个链表即可

/*** 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* getIntersectionNode(ListNode* headA, ListNode* headB) {// 如果任何一个链表为空，直接返回 nullptrif (headA == nullptr || headB == nullptr){return nullptr;}// 使用两个指针 pA 和 pB 分别遍历链表 A 和链表 BListNode* pA = headA;ListNode* pB = headB;// 遍历两个链表，直到两个指针指向相同节点或都为 nullptrwhile (pA != pB) {// 如果 pA 到达链表 A 的末尾，重新指向链表 B 的头节点pA = pA == nullptr ? headB : pA->next;// 如果 pB 到达链表 B 的末尾，重新指向链表 A 的头节点pB = pB == nullptr ? headA : pB->next;}// 返回交点节点，如果没有交点，则返回 nullptrreturn pA;}
};

解法：这题思路有点儿像我们小学当中的列竖式，两个链表的头结点即结果的个位，下一个结点即十位，依次下去就是百位，千位，依次推……，所以简单来说这题就是模拟，不过模拟的是链表中的竖式运算。

class Solution 
{
public:// 将两个数字以链表形式相加ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {// 初始化两个链表指针ListNode* cur1 = l1, *cur2 = l2;// 创建一个虚拟头结点，用于方便处理链表的拼接ListNode* newhead = new ListNode();// prev 是尾指针，指向当前链表的末尾节点ListNode* prev = newhead;// 使用 t 来表示进位，初始化为 0int t = 0;// 只要两个链表还有节点或进位不为 0，就继续加法运算while (cur1 || cur2 || t){// 如果 cur1 不为空，将 cur1 的值加到进位 t 中if (cur1){t += cur1->val;cur1 = cur1->next;}// 如果 cur2 不为空，将 cur2 的值加到进位 t 中if (cur2){t += cur2->val;cur2 = cur2->next;}// 将当前位的和（个位）存入新节点prev->next = new ListNode(t % 10);// 更新进位，t // 10 即为进位的值t /= 10;// 移动 prev 指针prev = prev->next;}// 获取链表的实际头结点，跳过虚拟头结点prev = newhead->next;// 释放虚拟头结点的内存delete newhead;// 返回链表的实际头结点return prev;}
};

• 方法一：
  首先我们知道——给定一个单链表，每两个相邻的节点交换位置，返回交换后的链表。如果链表的长度是奇数，最后一个节点保持不变。交换操作是局部的：仅仅交换每对相邻节点。
  遍历链表时，每次交换一对相邻的节点。为了方便交换，我们可以使用指针 prev 来指向当前交换对的前一个节点。
  使用 cur 来指向当前节点，next 用来指向当前节点的下一个节点，nnext 用来指向下一个节点对的第一个节点，方便下一轮交换。
  我们要不断地更新这些指针，确保交换后的链表依然保持正确的顺序。

class Solution 
{
public:ListNode* swapPairs(ListNode* head) {// 如果链表为空或只有一个节点，则不需要交换if (head == nullptr || head->next == nullptr)return head;// 创建一个虚拟头节点，指向原链表的头节点ListNode* newhead = new ListNode();newhead->next = head;// 创建四个指针：prev（前驱指针）、cur（当前节点指针）、next（当前节点的下一个节点指针）、nnext（next的下一个节点指针）ListNode* prev = newhead, *cur = head, *next = head->next, *nnext = head->next->next;// 开始交换操作：一对一对地交换节点while (cur && next){// 交换 cur 和 next 这两个节点prev->next = next;   // prev 的下一个节点指向 next（即交换后的前一个节点）next->next = cur;    // next 的下一个节点指向 cur（即交换后的后一个节点）cur->next = nnext;   // cur 的下一个节点指向 nnext（即 cur 后面的节点）// 更新指针以继续下一对节点的交换prev = cur;          // prev 指向 cur（新的前驱节点）cur = nnext;         // cur 指向 nnext（新的当前节点）if (cur) next = cur->next; // 如果 cur 不为空，更新 nextif (next) nnext = next->next; // 如果 next 不为空，更新 nnext}// 返回交换后的链表的头节点，跳过虚拟头节点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* ret = head->next;// 递归交换后续链表的节点// 交换后续链表的节点，直到链表末尾ListNode* newnode = swapPairs(head->next->next);// 完成当前节点对的交换head->next->next = head;  // 将第二个节点的 next 指向第一个节点，完成交换head->next = newnode;     // 将第一个节点的 next 指向递归返回的新的链表（新的后续部分）// 返回新的头节点return ret;}
};

• 解法：首先使用快慢指针找到链表的中间节点，将链表分为两部分。然后将后半部分链表反转。接着，将前半部分链表和反转后的后半部分链表交替合并，确保前后部分节点交替排列。最终，返回合并后的链表即可。这个方法利用了快慢指针找到中点，反转后半部分链表，最后通过合并两个链表来完成重排。

class Solution 
{
public:void reorderList(ListNode* head) {// 基本情况：如果链表为空，或者链表长度小于等于 2，则无需操作if (head == nullptr || head->next == nullptr || head->next->next == nullptr)return;// 使用快慢指针找到链表的中间节点ListNode* fast = head, *slow = head;// 快指针一次走两步，慢指针一次走一步，直到快指针到达链表末尾while (fast && fast->next){fast = fast->next->next;slow = slow->next;}// 将 slow 后面的链表进行逆序（头插法）ListNode* newhead = new ListNode(); // 用来存储逆序链表的头节点ListNode* cur = slow->next; // cur 指向链表中间节点的下一个节点（逆序的起始节点）slow->next = nullptr; // 断开链表，慢指针处为链表的中间点while (cur){ListNode* next = cur->next; // 保存下一个节点cur->next = newhead->next;  // 头插法，将当前节点插到新链表的最前面newhead->next = cur;        // 更新新链表的头节点cur = next;                 // 更新当前节点}// 合并两个链表ListNode* ret = new ListNode(); // 用来存储最终的合并结果ListNode* prev = ret; // prev 用来指向合并后的链表的末尾ListNode* cur1 = head, *cur2 = newhead->next; // cur1 是原链表的头节点，cur2 是逆序链表的头节点while (cur1){prev->next = cur1;  // 将 cur1（原链表的节点）接到 prev 后面cur1 = cur1->next;  // 更新 cur1 指向原链表的下一个节点prev = prev->next;  // 更新 prev 指向合并后的链表末尾if (cur2) // 如果逆序链表还有节点{prev->next = cur2; // 将 cur2（逆序链表的节点）接到 prev 后面prev = prev->next;  // 更新 prev 指向合并后的链表末尾cur2 = cur2->next;  // 更新 cur2 指向逆序链表的下一个节点}}// 删除临时创建的链表头节点delete newhead;delete ret;}
};

• 解法：该问题可以通过分治法（递归）解决。首先，将 k 个链表两两分组，递归地合并每一对链表。每次合并两个已排序的链表，可以通过比较节点值，将较小的节点依次插入合并后的链表中。递归基准条件为：如果链表数组为空或只剩一个链表，直接返回该链表；否则，将链表数组分为左右两部分，分别递归地合并左右两部分的链表，再合并结果。最终，通过不断合并小部分的链表，得到最终的合并结果。

class Solution 
{
public:// 合并 k 个升序链表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 >> 1; // 递归合并左半部分ListNode* l1 = merge(lists, left, mid);// 递归合并右半部分ListNode* l2 = merge(lists, mid + 1, right);// 合并左右两部分链表return mergeTwoLists(l1, l2);}// 合并两个升序链表ListNode* mergeTwoLists(ListNode* l1, ListNode* l2){// 如果 l1 为空，返回 l2if (l1 == nullptr) return l2;// 如果 l2 为空，返回 l1if (l2 == nullptr) return l1;// 创建一个虚拟头结点，用于简化链表操作ListNode head;ListNode* cur1 = l1, *cur2 = l2, *prev = &head;// 合并两个链表，直到一个链表遍历完while (cur1 && cur2){// 比较 cur1 和 cur2 的值，选择较小的节点添加到合并链表中if (cur1->val <= cur2->val){prev = prev->next = cur1;  // 将 cur1 插入到合并链表cur1 = cur1->next;         // 更新 cur1}else{prev = prev->next = cur2;  // 将 cur2 插入到合并链表cur2 = cur2->next;         // 更新 cur2}}// 如果 cur1 还有剩余节点，直接连接到合并链表if (cur1) prev->next = cur1;// 如果 cur2 还有剩余节点，直接连接到合并链表if (cur2) prev->next = cur2;// 返回合并链表的头节点（跳过虚拟头结点）return head.next;}
};

• 解法：该问题可以通过分组反转链表的方式解决。首先计算链表的总长度，并根据给定的 k 值确定可以反转的完整组数。然后，遍历链表，每次取出 k 个节点进行反转。具体操作是通过将当前节点插入到前一个节点的后面来实现反转。对于每个反转后的组，将其连接到前一组的末尾，最后处理剩余节点（如果不足 k 个节点则不反转）。反转过程通过虚拟头节点简化了头节点的处理，最终返回反转后的链表。

class Solution 
{
public:// 每k个节点反转一次链表ListNode* reverseKGroup(ListNode* head, int k) {// 计算链表中节点的总数int n = 0;ListNode* cur = head;while(cur){cur = cur->next;n++;}// 计算可以进行反转的组数n /= k;// 创建一个虚拟头节点，用于简化链表操作ListNode* newhead = new ListNode();ListNode* prev = newhead;  // prev 用于连接反转后的链表部分cur = head;// 遍历链表并按 k 个节点进行反转for(int i = 0; i < n; i++){// 临时保存当前组的第一个节点ListNode* tmp = cur;// 对当前组的 k 个节点进行反转for(int j = 0; j < k; j++){// 保存当前节点的下一个节点ListNode* next = cur->next;// 将当前节点插入到 prev 之后cur->next = prev->next;prev->next = cur;// 更新 cur 为当前节点的下一个节点cur = next;}// prev 更新为当前组反转后的最后一个节点prev = tmp;}// 处理剩余的部分，如果节点数不足 k，保持原样连接prev->next = cur;// 返回反转后的链表头（跳过虚拟头节点）cur = newhead->next;delete newhead;  // 删除虚拟头节点return cur;}
};