• 「使用双指针技巧解决一些链表的问题」（每日刷题打卡Day31）[C++]

    文章目录

    141. 环形链表

    在这里插入图片描述

    题解

    使用双指针，一个快指针，一个慢指针，快指针fast一次走两步，而慢指针slow一次走一步，看会不会碰到，碰到了就说明有环。

    Code

    /**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (head == nullptr) return head;
        ListNode *fast = head, *slow = head;
        while (fast != nullptr && fast->next != nullptr)//走两步的指针都要看这个fast->next是否为空
        {
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow) return true;
        }
        return false;
    }
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    结果

    在这里插入图片描述

    142. 环形链表 II

    在这里插入图片描述

    题解

    还是使用双指针，一个快一个慢，当两个指针相遇碰到的时候，跳出循环，此时两个指针是相遇的时候跳出了循环，此时让slow = head，然后此时fast和slow再一起移动，再次相遇的时候，就是环的起点。

    Code

    /**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if (head == nullptr) return head;
        ListNode *fast = head, *slow = head;
        while (fast != nullptr && fast->next != nullptr)
        {
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow) break;
        }

        //判断是while循环跳出，还是if中的break跳出
        if (fast == nullptr || fast->next == nullptr) return nullptr;//说明没有环

        //如果不是从while中跳出，说明是从if跳出，此时是两者进入了相交点
        slow = head;//令solw = head，这时候，再让fast和slow同时走，再次相遇的点，就是环的起点
        while (fast != slow)
        {
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33

    结果

    在这里插入图片描述

    160. 相交链表

    在这里插入图片描述

    题解

    如何判断两个链表是否相交？我们可以让两个链表的长度相等，当到达相交节点的时候返回，那如何让两个长度不等的链表长度相等？可以等A跑完，再让A接着B跑，B跑完再让B接着A跑，就可以达到目的。

    Code

    /**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        //想办法让两链表长度一样，这样就能都找到这个相交点后停下
        ListNode *p1 = headA, *p2 = headB;
        while (p1 != p2)
        {
            if (p1 == nullptr) p1 = headB;
            else p1 = p1->next;
            if (p2 == nullptr) p2 = headA;
            else p2 = p2->next;
        }
        return p1;//相交的时候，就返回相交节点，p1或者p2都可以；不想交的时候，直到p1或p2都为空，跳出循环后，p1 = p2 =nullptr，返回空节点。
    }
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23

    结果

    在这里插入图片描述

    19. 删除链表的倒数第 N 个结点

    在这里插入图片描述

    题解

    删除倒数第n个节点，也就是删除正数第m-n+1个节点，m代表总的节点数，还是利用双指针，利用以上规律，先找到倒数第n+1个节点，找到后，进行删除倒数第n个。

    Code

    /**
 * 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* find(ListNode* head, int n)
    {
        ListNode *p1 = head;//采用双指针，p1先向前走n步
        for (int i = 0; i < n; ++i)
        {
            p1 = p1->next;
        }
        ListNode *p2 = head;
        //此时p2在第一个节点位置，此时p1已经走完n步了，现在让p1 p2同时开始走步，走m-n步即可。
        while (p1 != nullptr)
        {
            p2 = p2->next;
            p1 = p1->next;
        }
        //此时p2的位置，即为正数的m-n+1位置
        return p2;
    }

    ListNode* removeNthFromEnd(ListNode* head, int n) {
        //删除倒数第n个节点，也就是整数第m-n+1个节点，m是节点总数
        ListNode* dummy = new ListNode(-1);//引入dummy是为了防止出现空指针的问题，
        //比如说，就只有一个节点，但是需要删除倒数n+1的节点，也就是倒数第2的节点
        //一个节点拿来倒数第二的节点呢？所以引入虚拟头结点就很好地解决了这个问题
        dummy->next = head;
        ListNode *x = find(dummy, n+1);//找到倒数第n+1个节点
        x->next = x->next->next;
        return dummy->next;
    }
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41

    结果

    在这里插入图片描述

    21. 合并两个有序链表

    在这里插入图片描述

    题解

    两个链表从表头开始从左至右依次进行比较，再结合虚拟头结点，使两个链表合并。

    Code

    /**
 * 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* list1, ListNode* list2) {
        //大概思路，虚拟哨兵头结点以及这个双指针的框架
        ListNode* dummy = new ListNode(-1);
        ListNode* p = dummy;
        ListNode *p1 = list1, *p2 = list2;
        while (p1 != nullptr && p2 != nullptr)
        {
            if (p1->val > p2->val)
            {
                p->next = p2;
                p2 = p2->next;
            }
            else
            {
                p->next = p1;
                p1 = p1->next;
            }
            p = p->next;//指针向后移动
        }
        //假如最后还有两链表还有剩余
        if (p1 != nullptr)
        {
            p->next = p1;
        }
        if (p2 != nullptr)
        {
            p->next = p2;
        }
        return dummy->next; 
    }
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43

    结果

    在这里插入图片描述

    23. 合并K个升序链表

    在这里插入图片描述

    题解

    就是刚刚的合并两个的升级版，嵌套一个for循环，来进行合并。

    Code

    /**
 * 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 *a, ListNode *b)//通过构造每两个节点进行交换，推广到k个节点进行交换
    {
        if ((!a) || (!b)) return a?a:b;
        ListNode *dummy = new ListNode(-1);
        ListNode *p = dummy, *aPtr = a, *bPtr = b;
        while (aPtr && bPtr)
        {
            if (aPtr->val < bPtr->val)
            {
                p->next = aPtr;
                aPtr = aPtr->next;
            }
            else
            {
                p->next = bPtr;
                bPtr = bPtr->next;
            }
            p = p->next;
        }
        if (aPtr == nullptr)
        {
            p->next = bPtr;
        }
        if (bPtr == nullptr)
        {
            p->next = aPtr;
        }
        return dummy->next;
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode *ans = nullptr;
        for (size_t i = 0; i < lists.size(); ++i)//用个for循环，对每两个链表进行比较，这样就可以构造一个递增的序列
        {
            ans = mergeTwoLists(ans, lists[i]);
        }
        return ans;
    }
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51

    结果

    在这里插入图片描述

    86. 分隔链表

    在这里插入图片描述

    题解

    生成两个链表，一个小于x的，一个大于等于x的，接着再用上面合并两个链表的技术，进行合并这两个链表。

    Code

    /**
 * 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* partition(ListNode* head, int x) {
        //思路就是弄两个小链表，有什么作用呢？
        //这两个小链表，分别存放的是小于小于x的数，另一个存放的是大于等于x的数，最后将两个链表合并（参考第21题合并链表）
        //两个小链表就有两个虚拟头节点（哨兵）
        ListNode* dummy1 = new ListNode(-1);
        ListNode* dummy2 = new ListNode(-1);
        //双指针
        ListNode* p1 = dummy1;
        ListNode* p2 = dummy2;
        ListNode* p = head;
        ListNode* temp;

        while (p != nullptr)
        {
            if (p->val >= x)
            {
                p2->next = p;
                p2 = p2->next;
            }
            else
            {
                p1->next = p;
                p1 = p1->next;
            }
            //因为直接在原链表上操作，需要断开原链表中的每个节点的next指针，防止访问出错，因为不知道p指向哪里了
            temp = p->next;
            p->next = nullptr;
            p = temp;
        }

        //分解完后，开始整合
        p1->next = dummy2->next;

        return dummy1->next;
    }
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48

    结果

    在这里插入图片描述

    876. 链表的中间结点

    在这里插入图片描述

    题解

    有两种方法，一种是直接遍历两次，一次记录总节点数，一次到节点数/2的地方break；还有一种方法有点巧妙，双指针，快慢指针，fast走两步，slow走一步，然后fast走完，slow刚好是中点，而且，当节点数为偶数的时候，slow也是第二个中点。

    Code

    /**
 * 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* middleNode(ListNode* head) {
        ListNode* node = head;
        ListNode* low = head;
        if (head == nullptr) return head;
        int sum = 0, count = 0;
        while (node != nullptr)
        {
            node = node->next;
            ++sum;
        }
        while (count != sum / 2)    //使用两次循环判断
        {
            low = low->next;
            ++count;
        }
        return low;
    }
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    /**
 * 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* middleNode(ListNode* head) {
        //一样是采用双指针的技巧，设置fast还有slow这两个指针
        //fast一次走两步，slow一次走一步
        //当fast走到最后，slow刚好走到中点位置
        //同时，当节点数为偶数，slow也是刚好停到中间两节点第二个的那一个节点上
        if (head == nullptr)
        {
            return head;
        }
        ListNode *fast, *slow;
        fast = head;
        slow = head;
        while (fast != nullptr && fast->next != nullptr)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32

    结果

    在这里插入图片描述

    在这里插入图片描述
    两次遍历要慢一点。

  • 相关阅读:
    敏捷思维&敏捷管理工具
    Java多线程下载分析方法
    rocketmq消息写入流程
    Ajax 笔记/练习
    2023年华为杯研究生数学建模竞赛辅导
    JavaCard学习笔记： CAP Component 之 Class Component
    JavaScript循环语句（for、while）
    《DevOps实践指南》- 读书笔记（六）
    计算机毕业设计Python+Django的学生作业管理系统
    CSS选择器分类 [后代选择器、交集选择器、并集选择器(分组选择器)]
  • 原文地址：https://blog.csdn.net/weixin_44673253/article/details/126508527