首页 > 试题广场 >

环形单向链表

[编程题]环形单向链表
  • 热度指数: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");
}
}
#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)
#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)

热门推荐

通过挑战的用户