当前位置：首页 > article >正文

【初阶数据结构与算法】链表刷题之链表分割、相交链表、环形链表1、环形链表I、环形链表II

article 2024/11/18 8:36:37

在这里插入图片描述

文章目录

一、链表分割
二、相交链表
三、环形链表I
四、环形链表||

一、链表分割

题目链接：https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70

我们来看看链表分割的题目描述和它给出的函数：
在这里插入图片描述
这个题虽然是以C++形式来做，但是不用担心，我们知道在哪里写代码就可以了，就是题目提示的地方，这个属于C++类的知识，我们在后面的C++部分会详细介绍
接着我们回归正题，题目要求我们将链表分割开来，值小于x的节点要放在链表的左边，值大于等于x的节点要放在链表的右边，这个题该怎么做呢？
方法和双指针的算法有点类似，但是又不完全相同，我们可以创建两个新链表，一个存放比x小的节点，另一个存放比x大或者和x相等的节点，最后让小链表和大链表首位相连即可
这里我们要注意的是，如果我们创建的两个链表初始为空会发生什么，我们每次插入节点时，都要判断要插入的链表是否为空，空和非空的操作不一致，加上我们有两个新链表，操作起来更加的繁琐
所以我们还是用上之前学过的知识，怎么保证一个链表默认不为空？没错，就是在初始情况下创建一个哨兵位节点占位，它不存放有效的数据，单纯用来占位，这样我们在插入节点时就不需要去判断链表是否为空了
最后我们再来大致梳理一下解题思路，就是创建大小链表，同时创建哨兵位占位，然后遍历原链表，把值小于x的节点放在小链表，其它的放在大链表，最后让小链表和大链表首尾相连即可，题解如下：

ListNode* partition(ListNode* pHead, int x) 
    {
        ListNode* lesshead, *lesstail;
        ListNode* greaterhead, *greatertail;
        lesshead = lesstail = (ListNode*)malloc(sizeof(ListNode));
        greaterhead = greatertail = (ListNode*)malloc(sizeof(ListNode));
        ListNode* pcur = pHead;
        while(pcur)
        {
            if(pcur->val < x)
            {
                lesstail->next = pcur;
                lesstail = pcur;
            }
            else 
            {
                greatertail->next = pcur;
                greatertail = pcur; 
            }
            pcur = pcur->next;
        }
        //小链表的尾巴连接大链表的头
        //大链表哨兵位的下一个节点是真正的头
        lesstail->next = greaterhead->next;
        //为了避免形成环，把尾节点的next指针置为空
        greatertail->next = NULL;
        //要返回的头就是小链表哨兵位后真正的头
        ListNode* ret = lesshead->next;
        //资源清理工作
        free(lesshead);
        free(greaterhead);
        lesshead = NULL;
        greaterhead = NULL;
        return ret;
    }

我们提交一下试试：
在这里插入图片描述

二、相交链表

题目链接：https://leetcode.cn/problems/intersection-of-two-linked-lists/description/

我们来看看题目描述和给出的函数：
在这里插入图片描述

题目的要求就是给我们两个链表，然后让我们判断这两个链表是否相交，如果相交就返回相交的节点，否则就返回空
我们要注意到相交链表的特殊性，直线相交的话它们还会朝着不同的方向继续延伸，想象一下链表相交以后会怎么样，它们相交后一定只有一个方向，而不会像直线相交那样有多个方向，因为如果它们相交，那么相交节点的next指针指向同一个节点，如此循环下去自然就只有一个方向
那么问题好像要简单一些了，我们遍历两个链表，看看有没有相同的节点不就好了，可是还是有一个问题，我们看看题目的第一个示例就知道了：
在这里插入图片描述
这个问题就是两个链表的长度可能不同，在上面的示例中，如果同时开始遍历的话，当链表A遍历到相交节点8时，链表B才遍历到节点1，这样它们差一位就永远不能相等，也就找不到相交节点
那有没有什么办法让它们从同一起跑线出发呢？我们能让小的那个链表变长，但是可以让大链表往前走两步呀，比如上图，我们就可以让大链表先往前走一步到6节点，然后它们在同一起跑线往后遍历就可以找到相交节点了
问题是我们要怎么知道那个链表大，大多少，知道了这两个条件后，我们就可以让大链表提前走它们的长度差距，然后同时对他们进行遍历，为了知道它们的大小，我们可以定义两个整型计数器来计算它们的大小
然后根据大小来判断谁大谁小，然后让大链表往前走它们的长度差距，最后让大小链表同时往前遍历，如果遇到相同的节点说明它们相遇了，返回这个节点就可以了，但是如果遍历到尾结点后还没有相同的节点，说明两个链表不相交，返回空，题解如下：

typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
    //创建两个节点指针遍历链表
    ListNode* pcurA = headA;
    ListNode* pcurB = headB;
    int countA = 0, countB = 0;
    while(pcurA)
    {
        countA++;
        pcurA = pcurA->next;
    }
    while(pcurB)
    {
        countB++;
        pcurB = pcurB->next;
    }
    //假设法来判断链表大小
    //假设A链表更小
    //如果假设错误后面计算出大小后进行修改
    ListNode* lesslist = headA;
    ListNode* greaterlist = headB;
    //如果A的节点个数大于B，那么进行修改
    if(countA > countB)
    {
        lesslist = headB;
        greaterlist = headA;
    }
    //接着让大的链表往后走间隔大小
    //首先使用绝对值函数求间隔大小
    int size = abs(countA - countB);
    while(size--)
    {
        greaterlist = greaterlist->next;
    }
    //此时两个链表在同一起跑线，长度一样
    //然后再往后遍历
    while(lesslist)
    {
        if(lesslist == greaterlist)
        {
            return lesslist;
        }
        lesslist = lesslist->next;
        greaterlist = greaterlist->next;
    }
    //出了循环说明没有相交，返回NULL
    return NULL;
}

最后提交一下代码：
在这里插入图片描述

三、环形链表I

题目链接：https://leetcode.cn/problems/linked-list-cycle/description/

我们来看看环形链表I的题目描述与示例：
在这里插入图片描述
我们首先要知道链表带环是什么意思，就是它的尾结点的next指针不指向空了，而是指向链表中的某个节点，以此成为带环链表
这个题还较为简单，只需要我们判断链表是否有环，而不需要我们找出入环节点，做这个题需要用到一个结论，这里我就直接说出来了，如果对它的证明过程感兴趣可以自行去了解一下，当然也可以私信我，我会及时给出解答，这里就不多证明了
在这里我们需要用到快慢指针，结论就是慢指针一次走一步，快指针一次走两步，如果链表带环，那么快指针和慢指针一定会在环内相遇，如果不带环那么循环直接结束了，有了这个结论我们写起来就简单多了，如下：

typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head) 
{
    ListNode* slow = head;
    ListNode* fast = head;
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast)
        {
            return true;
        }
    }
    return false;
}

我们提交代码试试：
在这里插入图片描述

四、环形链表||

题目链接：https://leetcode.cn/problems/linked-list-cycle-ii/description/

我们来看看环形链表II的题目描述和示例：
在这里插入图片描述

这个题和上一个题的最大区别就是，这个题不仅要求我们判断链表是否是一个带环链表，如果带环还要我们找出入环的第一个节点，这个就比较难了
这里我们还是使用一个结论，相关的证明可以自行了解，也可以私信我，我会及时给出解答，这里就不多证明了
结论还是需要用到快慢指针，如果链表带环，那么快慢指针一定就会在环内相遇，并且相遇节点到入环节点的距离，和头结点到入环节点的距离相等
通俗一点说就是，当快慢指针在环内相遇后，让头结点和慢指针同时往前，并且每次走一步，那么当头结点和慢指针相遇时，相遇节点就是入环节点
因为此时头结点和慢指针走的步数相同，还相遇了，根据上面的结论就可以说明相遇节点就是入环节点，是不是特别神奇，接着我们就根据这个结论来写代码，如下：

typedef struct ListNode ListNode;
struct ListNode *detectCycle(struct ListNode *head) 
{
    ListNode* slow = head;
    ListNode* fast = head;
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast)
        {
            //进入这里说明链表带环
            ListNode* pcur = head;
            while(pcur)
            {
                //判断是否相等
                //不相等循环的往前走
                if(pcur == slow)
                {
                    return pcur;
                }
                pcur = pcur->next;
                slow = slow->next;
            }
        }
    }
    //出了循环，说明链表不带环
    return NULL;
}