程序员社区

力扣每日一题——NO.142环形链表2

题目原代码和图解已上传至我的码云

题目描述

给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。

为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。注意,pos 仅仅是用于标识环的情况,并不会作为参数传递到函数中。

说明:不允许修改给定的链表。

进阶:
你是否可以使用 O(1) 空间解决此题?

思路求解

这道题我们有两个思路去解决

第一种思路

我们在前面的文章中,已经讲到了判断环形链表的方法

点我直达前面的文章

这篇文章中,记得我们的slow指针和fast指针最终会重叠,对吧?

在这里插入图片描述
我们可以将这个问题转化为求相交链表的问题

点我查看相交链表的解法

将meet点的next断开,作为一个新的链表
在这里插入图片描述
这样我们就有了两个不同的链表,原来的环形链表和我们断开的链表结点的下一个结点newhead

这样就转化成了W我们的链表相交问题

//这个函数是判断相交的函数,由于上篇文章我们介绍过了,所以就可以直接拿来复用
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode* curA=headA,*curB=headB;
    int cntA=1;
    int cntB=1;
    while(curA->next)
    {
        cntA++;
        curA=curA->next;
    }
    

    while(curB->next)
    {
        cntB++;
        curB=curB->next;
    }
    if(curA!=curB)
        return NULL;

    struct ListNode* longlist=cntA>cntB?headA:headB;
    struct ListNode* shortlist=cntA>cntB?headB:headA;

    int dis=abs(cntA-cntB);

    while(dis--)
    {
        longlist=longlist->next;
    }

    while(longlist!=shortlist)
    {
        longlist=longlist->next;
        shortlist=shortlist->next;
    }
    return longlist;

}

//函数逻辑
struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode* slow=head,*fast=head;
    struct ListNode* meetNode=NULL;
    while(fast&&fast->next)
    {
        
        fast=fast->next->next;
        slow=slow->next;
        if(fast==slow)
        {
            meetNode=fast;
            break;
        }
        
    }
    if(!meetNode)
        return NULL;
    struct ListNode* rhead=meetNode->next;
    meetNode->next=NULL;
    return getIntersectionNode(head,rhead);
}

第二种方法

这个方法需要一定的数学证明

先给出结论吧~

如果我们在上文中提到的相遇点开始,与链表头结点同时以相同的速度往后遍历,它们一定能在入口处相遇

证明过程:

假设我们已经找到了meet点

在这里插入图片描述
设head到入口的距离为l,入口到meet的距离为x圈长为c

在这里插入图片描述

在meet相遇前,我们有:
fast指针已经走了L+nc+x步(nc是指fast在相遇前可能已经走了很多圈了)

slow指针走了L+X步

然后根据2slow=fast(上文已提到,我们有以下的等量关系)

2(L+X)=(L+nc+X)

解出L后,有:L=nc-x

nc-x就是环中x的剩余部分

在这里插入图片描述

所以我们有,L和c-x是相等的

所以原式我们得证

代码实现

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode* slow=head,*fast=head;
    struct ListNode* meetNode=NULL;
    while(fast&&fast->next)
    {
        
        fast=fast->next->next;
        slow=slow->next;
        if(fast==slow)
        {
            meetNode=fast;
            break;
        }
        
    }
    if(!meetNode)
        return NULL;
    
    struct ListNode* cur=head;
    while(meetNode!=cur)
    {
        cur=cur->next;
        meetNode=meetNode->next;
    }
    return cur;
}

赞(0) 打赏
未经允许不得转载:IDEA激活码 » 力扣每日一题——NO.142环形链表2

一个分享Java & Python知识的社区