首页 > 试题广场 >

环形单向链表

[编程题]环形单向链表

热度指数：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

输入

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");
}
}