首页 > 试题广场 >

链表中环的入口结点

[编程题]链表中环的入口结点
  • 热度指数：646153 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。

数据范围： ，
要求：空间复杂度 ，时间复杂度

例如，输入{1,2},{3,4,5}时，对应的环形链表如下图所示：

可以看到环的入口结点的结点值为3，所以返回结点值为3的结点。

输入描述:
输入分为2段，第一段是入环前的链表部分，第二段是链表环的部分，后台会根据第二段是否为空将这两段组装成一个无环或者有环单链表


输出描述:
返回链表的环的入口结点即可，我们后台程序会打印这个结点对应的结点值；若没有，则返回对应编程语言的空结点即可。
示例1

输入

{1,2},{3,4,5}

输出

3

说明

返回环形链表入口结点，我们后台程序会打印该环形链表入口结点对应的结点值，即3
示例2

输入

{1},{}

输出

"null"

说明

没有环，返回对应编程语言的空结点，后台程序会打印"null"
示例3

输入

{},{2}

输出

2

说明

环的部分只有一个结点，所以返回该环形链表入口结点，后台程序打印该结点对应的结点值，即2

说明：本题目包含复杂数据结构ListNode，点此查看相关信息
算法知识视频讲解
查看答案及解析
添加回答
推荐
Top_bo头像 Top_bo
如果链表中环 有n个结点，指针P1在链表上向前移动n步，然后两个指针以相同的速度向前移动。
 当第二个指针指向环的入口结点时，第一个指针已经围绕着环走了一圈又回到了入口结点。
所以首先要得到环中结点的数目。

public class 链表中环的入口结点 {
	//找到一快一满指针相遇处的节点，相遇的节点一定是在环中
	public static ListNode meetingNode(ListNode head) {
		if(head==null)
			return null;
		
        ListNode slow = head.next;
        if(slow==null)
        	return null;
        
        ListNode fast = slow.next;
        while (slow != null && fast != null) {
        	if(slow==fast){
        		return fast;
        	}
        	slow=slow.next;
        	fast=fast.next;
        	
        	if(fast!=slow){
        		fast=fast.next;
        	}
        }
		return null;
    }
	public ListNode EntryNodeOfLoop(ListNode pHead) {
		ListNode meetingNode=meetingNode(pHead);
		if(meetingNode==null)
			return null;
//		得到环中的节点个数
		int nodesInLoop=1;
		ListNode p1=meetingNode;
		while(p1.next!=meetingNode){
			p1=p1.next;
			++nodesInLoop;
		}
//		移动p1
		p1=pHead;
		for(int i=0;i<nodesInLoop;i++){
			p1=p1.next;
		}
//		移动p1，p2
		ListNode p2=pHead;
		while(p1!=p2){
			p1=p1.next;
			p2=p2.next;
		}
		return p1;
	}
}

编辑于 2015-08-25 11:27:14 回复(45)
C
徐文达头像 徐文达 
typedef struct ListNode ListNode;
ListNode* EntryNodeOfLoop(ListNode *head)
{
    //没有结点，则无所谓环，更无所谓pos
    if(!head)
    {
        return NULL;
    }

    ListNode* slow = head;
    ListNode* fast = head;
    ListNode* meet = head;

    while(fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        
        //有环，进入找pos环节
        if(fast == slow)
        {
            while(meet != slow)
            {
                meet = meet->next;
                slow = slow->next;
            }
            return meet;
        }
    }
    //走到这里，说明没环
    return NULL;
}

编辑于 2024-03-30 11:07:37 回复(0)
C
一个优雅的程序猿头像 一个优雅的程序猿 
struct ListNode* EntryNodeOfLoop(struct ListNode* pHead ) {
    struct ListNode *buffer[10000], *p1=pHead;
    int bufferLen=0;
    if(pHead==NULL)
        return NULL;
    while(p1->next!=NULL) {
        int i;
        for(i=0;i<bufferLen;i++) {
            if(p1==buffer[i])
                return buffer[i];
        }
        buffer[i] = p1;
        bufferLen++;
        p1 = p1->next;
    }
    return NULL;
}

编辑于 2024-03-15 12:19:57 回复(0)
C
想去杭州的高级磨洋工在学习头像 想去杭州的高级磨洋工在学习

struct ListNode* EntryNodeOfLoop(struct ListNode* pHead ) {
    struct ListNode* fast=pHead;
    struct ListNode* slow=pHead;
    if(fast->next==NULL)
    {
        return NULL;
    }
    fast=fast->next->next;
    slow=slow->next;
    while(fast)
    {
        fast=fast->next->next;
        slow=slow->next;
        if(fast==slow)
        {
            break;
        }
    }
    if(fast==NULL)
    {
        return NULL;
    }
    fast=pHead;
    while(!(fast==slow))
    {
        fast=fast->next;
        slow=slow->next;
    }
    return fast;
}
编辑于 2024-03-02 20:54:38 回复(1)
C
计算机里打灰的头像 计算机里打灰的 
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param pHead ListNode类 
 * @return ListNode类
 */
 #include <stdio.h>
bool find(struct ListNode* pHead ){
        struct ListNode* fast=pHead;
        struct ListNode* slow=pHead;
        while(fast!=NULL && slow!=NULL){
            if(fast->next!=NULL){
                fast=fast->next->next;

            }else{
                return false;
            }
            slow=slow->next;
            if(slow==fast){
                return true;
            }
        }
        return false;
 }
 struct ListNode* cai(int v){
        struct ListNode* round=(struct ListNode*)malloc(sizeof(struct ListNode));
        round->val=v;
        round->next=NULL;
        return round;
 }
struct ListNode* EntryNodeOfLoop(struct ListNode* pHead ) {
    // write code here
    struct ListNode* node=pHead;
    struct ListNode* round=(struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* kk=(struct ListNode*)malloc(sizeof(struct ListNode));    
    kk=round;
    int i=0;
   
    struct ListNode* nullnode=NULL;   
    if(!find(pHead)){
        return nullnode;
    }else{
        while(1){
            struct ListNode* ff=kk->next;
            while(ff!=NULL){
                if(ff->val==node->val){
                   return ff;
                }
                ff=ff->next;

            }
            round->next=cai(node->val);
            round=round->next;
            node=node->next;


            
        }
    }

}

编辑于 2024-01-17 21:41:20 回复(0)
C
A202302282044461头像 A202302282044461
struct ListNode* EntryNodeOfLoop(struct ListNode* pHead ) {
    // write code here
    struct ListNode * fast = pHead;
    struct ListNode * slow = pHead;

    while (fast && fast->next && fast->next->next) {
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow) {
            fast = pHead;
            while (fast != slow) {
                fast = fast->next;
                slow = slow->next;
            }
            return fast;
        }
    }
    return NULL;
}
发表于 2023-09-04 16:09:34 回复(0)
C
海涛的转不动的脑子很想转头像 海涛的转不动的脑子很想转
 static int s[10001]={0};
struct ListNode* EntryNodeOfLoop(struct ListNode* pHead ) {
    // write code here
    while(pHead)
    {
        if(s[pHead->val]==2)
        {
            return pHead;
        }
        s[pHead->val]++;
        pHead=pHead->next;
    }
    return NULL;
}
发表于 2023-08-12 09:02:15 回复(0)
C
不愿吃饼的小龙虾很幸福头像 不愿吃饼的小龙虾很幸福
struct ListNode* EntryNodeOfLoop(struct ListNode* pHead ) {
    // write code here
    struct ListNode *a=pHead,*b=pHead;
    int t=0;
    while((a->next!=NULL&&a!=NULL))
    {
        if(a!=b)
            {
                a=a->next->next;
                b=b->next;
            }
        else{
        if(a!=pHead||t!=0)
        {
           break;
        }
        else {
            a=a->next->next;
            b=b->next;
            t++;
        }
        }
    }
    printf("o");
    if(a->next==NULL||a==NULL)
        return NULL;
    struct ListNode *c=a;
    a=pHead;
    while (a!=c)
    {
        a=a->next;
        c=c->next;
    }
    return a;
}
为什么加了个printf就过了？不加就是段错误
发表于 2023-05-08 20:59:36 回复(0)
C
不放弃的放鸽子能手很想熬夜头像 不放弃的放鸽子能手很想熬夜
循环查找是否有相同结点 
struct ListNode* EntryNodeOfLoop(struct ListNode* pHead ) {
    // write code here
    struct ListNode* p = pHead;
    struct ListNode* q = pHead;

    while (p->next != NULL)
    {
        q = pHead;
        p = p->next;
        while (true)
        {
            if(q == p->next)
            {
                return q;
            }
            if(q == p)
            {
                break;
            }
            q = q->next;
        }
    }
    return NULL;
}

发表于 2023-04-04 09:46:12 回复(1)
C
帅奶哟。头像 帅奶哟。 
struct ListNode* EntryNodeOfLoop(struct ListNode* pHead ) {
    // write code here
    //s数组用于记录出现次数
    int s[10001] = {0};
    while (pHead) {
        //出现第二次时则是入口结点
        if (s[pHead->val] == 2) return pHead;
        //对应s下标的值++
        s[pHead->val]++;
        pHead = pHead->next;
    }
    return NULL;
}

发表于 2023-03-19 17:03:23 回复(0)
C
牛客885968742号头像 牛客885968742号 
struct ListNode* EntryNodeOfLoop(struct ListNode* pHead ) {
    struct ListNode*p1=pHead,*p2=pHead,*r=pHead;
    while(p1&&p2){
        p1=p1->next;
        p2=p2->next;
        if(p2) p2=p2->next;
        if(p1==p2&&p1){ 
            while(p1!=r){
            r=r->next;
            p1=p1->next;
        }
        return r;
        }
    }
    return NULL;
}

发表于 2023-03-17 22:17:42 回复(0)
C
一袋米扛二楼头像 一袋米扛二楼
struct ListNode* EntryNodeOfLoop(struct ListNode* pHead ) {
    // write code here
    if(pHead == NULL || pHead->next == NULL)
        return NULL;
    struct ListNode* p = pHead;
    struct ListNode* q = p->next;
    int i=0;
    while(1)
    {
        q = q->next;
        i++;
        if(q == NULL)
            return NULL;
        if(q == p)
            return p;
        if(i > 10000)
        {
            p = p->next;
            i=0;
        }
    }
    return NULL;
}
发表于 2023-03-08 20:51:44 回复(0)
C
YingQ头像 YingQ 
//这个不是一般的好理解，不用一步两步
struct ListNode* EntryNodeOfLoop(struct ListNode* pHead ) {
    // write code here
    int i=0;
    struct ListNode*pre=pHead;
    struct ListNode*temp=pHead;

    while(pre!=NULL){
        pre=pre->next;
        i++;
        if(i>10000) break;
    }
    if(i<10000) return NULL;
    while(temp->val>0){
        temp->val=temp->val-10000;
        temp=temp->next;
    }
    struct ListNode*head=temp;
        while(temp->val<1){
        temp->val=temp->val+10000;
        temp=temp->next;
    }
    return head;
    
}

发表于 2023-03-08 17:39:13 回复(0)
C
天外来客头像 天外来客
因为节点值[1， 10000]
因此，依次遍历节点，将节点值取反(*-1)，
如果遇到next节点值<0，则该节点为环的入口，
将该节点值再次取反，并返回该节点即可。 

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param pHead ListNode类 
 * @return ListNode类
 */
struct ListNode* EntryNodeOfLoop(struct ListNode* pHead ) {
    // write code here
    //空链表和单个节点链表直接返回
    if(!pHead || !pHead->next)
        return NULL; 

    /*
        因为节点值[1， 10000]
        因此，依次遍历节点，将节点值取反(*-1)，
        如果遇到next节点值<0，则该节点为环的入口，
        将该节点值再次取反，并返回该节点即可。
    */
    while(pHead)
    {
        if(pHead->val  < 0)
        {
            pHead->val *= (-1);
            return pHead;
        }
        pHead->val *= (-1);
        pHead = pHead->next;
    }

    return NULL;
}
发表于 2023-01-30 18:07:26 回复(0)
C
Hayaizo头像 Hayaizo 
struct ListNode* EntryNodeOfLoop(struct ListNode* pHead ) {
    struct ListNode*fast=pHead;
    struct ListNode*slow=pHead;
    while(fast&&fast->next){
        fast=fast->next->next;
        slow=slow->next;
        if(fast==slow){
            struct ListNode* tmp=pHead;
            while(tmp!=slow){
                tmp=tmp->next;
                slow=slow->next;
            }
            return tmp;
        }
    }
    return NULL;
}

发表于 2022-09-09 13:30:39 回复(0)
C
牛客572130657号头像 牛客572130657号
每次让当前节点的指针域指向自己，如果有环，则入口节点满足条件指针域指向自己


发表于 2022-05-22 22:04:19 回复(0)
C
和覅wEJVB头像 和覅wEJVB
struct ListNode* EntryNodeOfLoop(struct ListNode* pHead ) 
{
    struct ListNode *fast=pHead;
    struct ListNode *slow=pHead;
    while(fast && fast->next)
    {
        fast=fast->next->next;
        slow=slow->next;
        if(fast==slow)
        {
            struct ListNode *meet=slow;
            while(meet!=pHead)
            {
                meet=meet->next;
                pHead=pHead->next;
            }
            return meet;
        }
    }
    return NULL;
}
//方法：指针从相遇点开始走，另一个从pHead走，他们会在入口点相遇
发表于 2022-03-23 18:39:22 回复(0)
提交观点

问题信息

链表 哈希 双指针
难度：
23条回答 129896浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号