【LeetCode&牛客&数据结构】单链表的应用——环形链表及链表分割问题详解

用户11831438

发布于 2025-12-30 12:32:24

1200

前言：各位uu们，在刷题的时候，要多画图，画图有利于我们更快的思考出相应的解题思路！！！

正文

一、环形链表1

141. 环形链表 - 力扣（LeetCode）

1、题目描述

2、思路及代码

思路：设置两个指针，一个快指针，一个慢指针，快指针每次走两步，慢指针每次走一步，比较来两个指针，如果相等，则说明有环；否则没有环。

将上面思路转换成代码：

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

若有uu对循环条件不清楚的，可以看一下上面的链表的中间节点思路2。

3、结论及证明

思考1：为什么快指针每次走两步，慢指针走一步可以相遇，有没有可能遇不上，请推理证明！

因此，在带环链表中慢指针走一步，快指针走两步最终⼀定会相遇。

思考2：快指针⼀次走3步，走4步，...n步行吗?

所以，不管fast每次走几步，一定会相遇。

4、其他思路

我们也可以创建数组：

二、环形链表2

142. 环形链表 II - 力扣（LeetCode）

1、题目描述

示例

2、思路及代码

思路：首先判断链表是否有环（快慢指针），快慢指针找相遇点，相遇点到入环结点的距离==头结点到入环结点的距离。

将上面的思路转换成代码：

typedef struct ListNode ListNode;
struct ListNode *detectCycle(struct ListNode *head) {
    ListNode* slow=head;
    ListNode* fast=head;
    while(fast!=NULL&&fast->next!=NULL)
    {
        slow=slow->next;
        fast=fast->next->next;
        if(slow==fast)
        {
            //说明有环，快慢指针相遇
            //相遇点到入环结点的距离==头结点到入环节点的距离
            ListNode* pcur=head;
            while(pcur!=fast)
            {
                pcur=pcur->next;
                fast=fast->next;
            }
            return fast;
        }
    }
    return false;
}

3、结论及证明

通过这题我们可以得出一个结论：

接下来，我们可以尝试证明一下这个结论

三、链表分割

链表分割_牛客题霸_牛客网

1、题目描述

2、解题思路

思路：创建两个新的头点，作为“哨兵位”，遍历原链表，比较结点中的值与x的大小，一个链表中放比x大的值，另一个链表放比x小的值，最后将这两个链表相连接，返回小的链表的头结点。

3、思路转换成代码

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
#include <cstddef>
#include <random>
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        // write code here
        ListNode* lessHead,*lessTail;
        ListNode* greatHead,*greatTail;
        lessHead=lessTail=(ListNode*)malloc(sizeof(ListNode));
        greatHead=greatTail=(ListNode*)malloc(sizeof(ListNode));
        //遍历链表，比较大小
        //大的放大链表中，小的放小链表中
        ListNode* pcur=pHead;
        while(pcur)
        {
            if(pcur->val<x)
            {
                lessTail->next=pcur;
                lessTail=lessTail->next;
            }
            else {
            greatTail->next=pcur;
            greatTail=greatTail->next;
            }
            pcur=pcur->next;
        }
        //链接两个链表
        lessTail->next=greatHead->next;
        greatTail->next=NULL;
        ListNode* ret=lessHead->next;
        free(lessHead);
        free(greatHead);
        lessHead=NULL;
        greatHead=NULL;
        return ret;
    }
};