首页 > 试题广场 >

环形单向链表

[编程题]环形单向链表
  • 热度指数：133 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
给一个单向链表，若其中包含环，请完善EntryNodeOfLoop方法找出该链表的环的入口结点，否则，输出null。要求空间复杂度为O(1)
public class ListNode {  //链表的数据结构
   int val;
   ListNode next = null;
}
public ListNode EntryNodeOfLoop(ListNode pHead) {

}


输入描述:
第一行输入整数n(1<=n<=100)表示链表的结点数。

第二行n个整数，第i个整数表示结点i指向的下一个结点，0表示null。

保证从链表1开始，保证最多只有一个入口结点。


输出描述:
如果存在循环输出入口编号。
如果不存在输出NULL。
示例1

输入

4
2 3 4 2

输出

2
示例2

输入

5
2 3 4 5 0

输出

NULL

备注:
以下为java输入的示例，仅需正确补写EntryNodeOfLoop函数即可。对于其他语言可类似的自行实现。

import java.util.Scanner;

public class Main {
public static class ListNode {
int val;
ListNode next = null;
}
public static ListNode EntryNodeOfLoop(ListNode pHead) {
// to be completed
}

public static ListNode[] x = new ListNode[101];

public static void main(String args[]) {
Scanner s = new Scanner(System.in);
int n = s.nextInt();
x[0] = null;
for (int i=1;i<=n;i++) x[i]=new ListNode();
for (int i=1;i<=n;i++) {
int nex = s.nextInt();
x[i].val = i;
x[i].next = x[nex];
}
ListNode ans = EntryNodeOfLoop(x[1]);
if (ans != null) System.out.println(ans.val);
else System.out.println("NULL");
}
}
算法知识视频讲解
添加回答
neekity头像 neekity
https://blog.csdn.net/weixin_40807247/article/details/91447922
发表于 2019-09-16 16:45:10 回复(0)
牛客大聪明头像 牛客大聪明
#include<iostream>
#include<set>
using namespace std;

int main(){
    int num;
    int temp;
    set<int> _set;
    cin >> num;
    for(int i=0;i<num;i++){
        cin >> temp;
        if(temp == 0){
            cout << "NULL" << endl;
            return 0;
        }
        if(_set.empty()){
            _set.insert(temp);
            continue;
        }
        set<int>::iterator it = _set.find(temp);
        if(it != _set.end()){
            cout << temp << endl;
            return 0;
        } else {
            _set.insert(temp);
        }
    }
    cout << "NULL" << endl;
    return 0;
}
发表于 2022-04-08 07:16:06 回复(0)
光辉岁月v头像 光辉岁月v 
#include<iostream>
#include<algorithm>
#include<string>
#include <vector>
#include<map>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
};


ListNode* EntryNodeOfLoop(ListNode* pHead) {
    ListNode* p = pHead;
    map<int,int>m;
    while(p){
        if(m.count(p->val)==0){
            m.insert(make_pair(p->val,1));
        }else{
            break;
        }
        
        p=p->next;
    }
    if(!p){
        return NULL;
    }else{
        ListNode* q = pHead;
        while(q->val != p->val){
            q=q->next;
        }
        return q;
    }
    
}
int main(){
    int n;
    cin>>n;
    int i;
    struct ListNode*head = NULL;
    struct ListNode*p,*q;
    for(i=0;i<n;i++){
        p = new ListNode;
        cin>>p->val;
        p->next = NULL;
        if(head == NULL){
            head = p;
            q = p;
        }else{
            q->next = p;
            q = p;
        }
    }
    p = EntryNodeOfLoop(head);
    if(p){
        cout<<p->val;
    }else{
        cout<<"NULL";
    }
    
}

编辑于 2020-08-03 11:03:31 回复(0)
提交观点

问题信息

C++工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 安全工程师 c#工程师 数据库工程师 瓜子二手车 2019 大数据开发工程师 Java工程师
上传者：小小
难度：
3条回答 2358浏览

热门推荐

通过挑战的用户

相关试题

环形单向链表

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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