问题描述:
有一个链表集合:List<node>,其中node对象表示如下:
public node
{
int currNodeID, //当前节点编号
int nextNodeID //下一节点编号
}
节点间通过nextNodeID串起来。
链表集合中杂乱的存放这好多node对象,也就是说链表集合中存在若干条通过node对象串起来的链表。具体问题:
请问如何判断这个链表集合中是否存在死链,即死循环?(最好给出具体的代码),谢谢。
有一个链表集合:List<node>,其中node对象表示如下:
public node
{
int currNodeID, //当前节点编号
int nextNodeID //下一节点编号
}
节点间通过nextNodeID串起来。
链表集合中杂乱的存放这好多node对象,也就是说链表集合中存在若干条通过node对象串起来的链表。具体问题:
请问如何判断这个链表集合中是否存在死链,即死循环?(最好给出具体的代码),谢谢。
从List集合中任一节点开始便利节点,将当前访问的节点存进一个哈希表,然后判断当前节点的nextNode是否存在哈希表中,如果存在则说明该链表是循环链表思路二:
从List集合中任一节点开始便利节点0(list.count),设置2个指针,一个指针每次进1为,另一个指针进2位,直到任一指针指向null,则说明该链表不是循环链表,如果指针1==指针2,则说明该链表是循环链表思路二复杂度小于思路一
而我那个List<node>是包含一个或多个链表的集合,我是不是要把列表中所有“当前节点”拿到,然后逐一进行你提供的思路?
---------------------
当前节点ID | 下一节点ID
---------------------
1 --> 2
2 --> 3
3 --> 4
4 --> 2
5 --> 6
6 --> 3如何判断?
3 --> 4
4 --> 2
这个就是死循环
但可以通过nextNodeID找出node集合列表。
比如:
List<node> nodeList = list.FindAll(m=>m.currNodeID=nextNodeID);
foreach(node item in nodeList)
{
//TODO:anything
}我只想通过这个集合判断是否存在死循环,如果能把具体的死循环找出来更好。