给一个单向链表,若其中包含环,请完善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。
4 2 3 4 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<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"; } }