暑期算法训练.11-EW帮帮网

//不带虚拟头结点
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        // 需要单独处理头节点,确保头结点不为空，并且里面的数值也不可以是空，头结点是个有效的头结点
        while (head != nullptr && head->val == val) {
            head = head->next;
        }
        // 再处理其他节点
        ListNode* cur = head;
        while (cur != nullptr && cur->next != nullptr) {
            if (cur->next->val == val) {
                cur->next = cur->next->next;
            }
            else {
                cur = cur->next;
            }
        }
        return head;
    }
};

这个是不带虚拟头结点的版本，可以看出来，咱们需要单独的处理一下头结点，然后再是处理其他的节点。并且，如果这样的话，步骤就比较繁琐，而且不容易统一处理方式

//带虚拟头结点的版本
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* dummy = new ListNode(0); // 虚拟头节点指向head
        dummy->next = head;
        ListNode* cur = dummy;
        while (cur->next != nullptr) {
            if (cur->next->val == val) {
                cur->next = cur->next->next; // 统一删除逻辑，直接跳过这个节点即可，也是单向链表通常的删除逻辑
            }
            else {
                cur = cur->next;
            }
        }
        return dummy->next; // 新头节点
    }
};

这个是带虚拟头结点的版本，是不是很爽，基本可以统一处理节点了（包括头节点）。

所以，虚拟头节点的好处就是：

1. 避免头节点的特殊处理

问题：在链表操作中，如果直接操作头节点（如删除、反转、插入等），通常需要额外判断：

如果删除头节点，需要重新指定 head。

如果插入新节点到头部，需要更新 head。

虚拟头结点的作用：

提供一个统一的“前驱节点”，使得头节点和其他节点的操作逻辑一致。

无论原头节点如何变化，dummy->next 始终指向新头节点。

2. 简化代码逻辑

没有虚拟头结点：需要单独处理头节点，代码分支增多。

有虚拟头结点：所有节点（包括原头节点）都有前驱节点，可以用统一逻辑处理。

在C++中，虚拟头节点一般这样创建：

ListNode* dummy = new ListNode(0); // 值任意，一般用0
dummy->next = head; // 指向原头节点
// ... 操作链表
return dummy->next; // 返回新头节点

3.不要吝啬空间，该创建的时候就得创建，这样可以省去不少的麻烦：

想必大家多多少少都做过这种题目吧，就是断开两个节点之间的链接，让第三个节点链接上去。那么此时，咱们如果不定义一个next节点变量，直接就有两个变量（prev，cur）去连接的话，此时就得注意一下顺序了。只能按照咱们图中所指的顺序来进行链接。

prev->next->prev=cur;
cur->next=prev->next;
prev->next=cur;
cur->prev=prev;

如果前两行与后两行颠倒了，先执行后两行，那么这样的话，会发现找不到后面那个节点了，也会导致cur->next=cur，自己指向自己，死循环。所以，这个时候就体现了，再定义一个新变量的必要性。再定义一个新变量，就不需要再担心执行的顺序了，管你先执行那个，都可以。

4.快慢指针

一般用于链表中环的判断，找到链表中环的入口，找到链表中倒数第n个节点。

而咱们链表的常用操作就是1.创建一个新的节点，2.尾插 3.头插（这个头插法在逆序链表中还是比较常用的）

这个是尾插，还是比较简单的。

这个是头插。相对于尾插来说，还是复杂一点的。

48. 力扣2.两数相加

48.1 题目解析：

这个题目有个关键的地方就是逆序操作，咱们可以直接从头开始加（因为这个是逆序存储的），即2,4,3 逆序存储为 3,4,2。5，6，4 逆序存储为4,6,5 。那么3，4，2与4，6，5相加，由于是从最低位开始加，那么逆序之后，对应的就从链表的头开始相加，非常的方便。

48.2 算法思路;

直接模拟两数相加即可

以上就是这个题目的所有的算法思路。

48.3 代码演示：

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) {
        ListNode* cur1 = l1; ListNode* cur2 = l2;
        ListNode* newnode = new ListNode(0);//创建一个虚拟头结点，记录最终结果
        int t = 0;
        ListNode* prev = newnode;
        while (cur1 || cur2 || t)
        {
            if (cur1)
            {
                t += cur1->val;
                cur1 = cur1->next;
            }
            if (cur2)
            {
                t += cur2->val;
                cur2 = cur2->next;
            }
            prev->next = new ListNode(t % 10);//新建一个节点才能去存储数字，因为此时newnode后面并没有节点。
            prev = prev->next;
            t /= 10;
        }
        ListNode* next = newnode->next;
        delete newnode;
        return next;
    }
};

48.4 总结反思：

这道题目充分的利用了上面的知识，所以还得具备充分的知识储备才可以。

49. 力扣24 两两交换链表中的节点

49.1 题目解析：

本题交换节点需要注意的是，不可以只交换节点里面的数值，必须得连着节点一起交换才可以。

49.2 算法思路：

OK，算法思路就是上面我写的这些，大家好好的参悟一下

49.3 代码演示：

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (head == nullptr || head->next == nullptr) return head;//若是链表为空，或者是链表只有一个元素，直接返回。注意，这里判断的标准时head，因为head才是真正的头结点，而不是newHead。判断这个的目的是为了预防下面的cur->next（cur为空，cur就是头结点，链表为空）与next->next（链表只有一个元素，此时next为空），空指针解引用
        ListNode* newHead = new ListNode(0);
        newHead->next = head;//head才是真正的头结点
        ListNode* prev = newHead;
        ListNode* cur = prev->next; ListNode* next = cur->next; ListNode* 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;
        }
        ListNode* kk = newHead->next;
        delete newHead;
        return kk;
    }
};

49.4 总结反思

其实这道题目也是用到了上面咱们所说的这些算法，大家还是得好好的参悟一下

50. 力扣 143 重排链表

50.1 题目解析：

这个题目其实是让你按照一定得顺序重新排一下链表

那么其实题目就是这样的，所以咱们可以分为三个步骤

1.找到链表的中间节点

使用快慢指针（一定要画图，考虑使用slow得落点在哪里）

2.把后面的部分逆序

使用双指针（或者三指针），或者头插法（推荐）完成逆序

3.合并两个有序链表，（双指针），按照一定得顺序合并

50.2 算法思路：

关于slow的落点，咱们直接砍掉slow后面的部分给逆序即可。不过需要引入虚拟头结点。一开始得先头插进第二个链表：

50.3 代码演示：

class Solution {
public:
    void reorderList(ListNode* head) {
        if (head == nullptr || head->next == nullptr || head->next->next == nullptr) return;
        //先找到中间节点
        ListNode* slow = head; ListNode* fast = head;
        while (fast && fast->next)//注意循环条件是这个，不是slow<fast
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        //之后使用头插法对slow后面的部分进行逆序
        ListNode* head2 = new ListNode(0);

        ListNode* cur = slow->next;
        slow->next = nullptr;
        while (cur)
        {
            ListNode* next = cur->next;//再定义一个变量存储这个cur，就是为了防止顺序问题
            cur->next = head2->next;
            head2->next = cur;
            cur = next;
        }
        //之后进行合并链表
        ListNode* kk = new ListNode(0);
        ListNode* prev = kk;
        ListNode* cur1 = head;
        ListNode* cur2 = head2->next;
        while (cur1)
        {
            //先合并第一个链表
            prev->next = cur1;
            cur1 = cur1->next;
            prev = prev->next;
            //再合并第二个链表
            if (cur2)
            {
                prev->next = cur2;

                prev = prev->next;
                cur2 = cur2->next;
            }
        }

        delete head2;
        delete kk;


    }
};

这样的代码量，放在整个链表对应的题目里面，算是比较多的了

50.4 总结反思

重点的东西还是开篇所讲的那些东西，还是希望大家要好好的研读，最好记住。

51 力扣 25 k个1组翻转链表

51.1题目解析：

其实这一题就考了一个模拟，并且也用到了逆序

51.2 算法思路：

51.3 代码演示：

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {

        //求出需要逆序多少组
        int n = 0;
        ListNode* cur = head;
        while (cur)
        {
            cur = cur->next;
            n++;
        }
        n /= k;

        //重复n次，将长度为k的链表逆序即可
        ListNode* newHead = new ListNode(0);
        ListNode* prev = newHead;
        ListNode* cur1 = head;
        for (int i = 0; i < n; i++)
        {
            ListNode* tmp = cur1;//把一开始的cur1的位置给存起来，由于是逆序存储，所以说后面的tmp的位置，就是下一组逆序头插的位置
            for (int j = 0; j < k; j++)//不可写成whilw(k--)
                /*k 被修改后没有恢复：内层 while (k--) 会直接修改 k 的值，导致后续循环（如果有）的 k 不正确。例如：

                第一次循环 k = 3，执行完 while (k--) 后 k = -1。

                如果还有第二次循环，k 已经变成 - 1，导致内层循环不执行，逻辑错误。

                n 被修改后不影响逻辑，但 k 被修改会导致后续组的反转次数错误。*/
            {
                ListNode* next = cur1->next;
                cur1->next = prev->next;
                prev->next = cur1;
                cur1 = next;
            }
            prev = tmp;
        }
        //剩下的直接接在后面即可
        prev->next = cur1;
        ListNode* cur2 = newHead->next;
        delete newHead;
        return cur2;
    }
};

这个地方，作者一开始写的时候，出现了一个失误，给大家看一下：

这个是错误的：
while(n--)  // 直接修改n的值
{
    ListNode* tmp = cur1;
    while(k--)  // 直接修改k的值
    {
        // 反转逻辑
    }
    prev = tmp;
}
问题：

k 被修改后没有恢复：内层 while(k--) 会直接修改 k 的值，导致后续循环（如果有）的 k 不正确。例如：

第一次循环 k=3，执行完 while(k--) 后 k=-1。

如果还有第二次循环，k 已经变成 -1，导致内层循环不执行，逻辑错误。

n 被修改后不影响逻辑，但 k 被修改会导致后续组的反转次数错误。
这个是正确的：
for(int i=0; i<n; i++)  // 不修改n
{
    ListNode* tmp = cur1;
    for(int j=0; j<k; j++)  // 不修改k
    {
        // 反转逻辑
    }
    prev = tmp;
}
改进点：

使用 for 循环代替 while 循环：

for(int j=0; j<k; j++) 不会修改 k 的值，确保每次反转都是 k 个节点。

for(int i=0; i<n; i++) 也不会修改 n，但即使修改 n 也不会影响逻辑。

避免了 k 被错误修改：

由于 k 保持不变，每次都能正确反转 k 个节点。

51.4 总结反思

今天的知识基本都用到了我在开篇所讲的那些知识

本篇完.................

暑期算法训练.11

47. 力扣203 移除链表元素

47.1 题目解析：

47.2 算法思路：

47.3 代码演示：