问题描述:
有一个链表集合:List<node>,其中node对象表示如下:
public node
{
   int currNodeID, //当前节点编号
   int nextNodeID  //下一节点编号
}
节点间通过nextNodeID串起来。
链表集合中杂乱的存放这好多node对象,也就是说链表集合中存在若干条通过node对象串起来的链表。具体问题:
请问如何判断这个链表集合中是否存在死链,即死循环?(最好给出具体的代码),谢谢。

解决方案 »

  1.   

    思路一:
          从List集合中任一节点开始便利节点,将当前访问的节点存进一个哈希表,然后判断当前节点的nextNode是否存在哈希表中,如果存在则说明该链表是循环链表思路二:
          从List集合中任一节点开始便利节点0(list.count),设置2个指针,一个指针每次进1为,另一个指针进2位,直到任一指针指向null,则说明该链表不是循环链表,如果指针1==指针2,则说明该链表是循环链表思路二复杂度小于思路一
      

  2.   

    谢谢,这是单链表的判断死循环的方式。
    而我那个List<node>是包含一个或多个链表的集合,我是不是要把列表中所有“当前节点”拿到,然后逐一进行你提供的思路?
      

  3.   

    这个结构是谁设计的?nextNodeID 存的是 node 在 List<node> 中的下标?
      

  4.   

    举个简单例子,比如:
    ---------------------
    当前节点ID | 下一节点ID
    ---------------------
    1    -->       2
    2    -->       3
    3    -->       4
    4    -->       2
    5    -->       6
    6    -->       3如何判断?
      

  5.   

    你怎么通过 nextNodeID  找到 nodeGetNodeByID(int nextNodeID) ?
      

  6.   

    2 --> 3
    3 --> 4
    4 --> 2
    这个就是死循环
      

  7.   

    我没有打算通过nextNodeID找出具体的node。
    但可以通过nextNodeID找出node集合列表。
    比如:
    List<node> nodeList = list.FindAll(m=>m.currNodeID=nextNodeID);
     foreach(node item in nodeList)
    {
       //TODO:anything
    }我只想通过这个集合判断是否存在死循环,如果能把具体的死循环找出来更好。
      

  8.   

    遍历全部currNodeID 判断在全部nextNodeID  是否存在,存在即循环链表 反之即单链表