使用C＃在鏈表中循環檢測

在面試問題中，「實現檢測循環存在的算法」。例如，鏈表有一個循環，如：使用C＃在鏈表中循環檢測

0--->1---->2---->3---->4---->5---->6 
       ▲     | 
       |     ▼ 
       11<—-22<—-12<—-9<—-8

使用Floyd的週期檢測，這個問題可以通過使用快速&慢指針來解決。所以我應該試着比較一下

a。 Link的節點值，即

if (fast.data == slow.data) 
    break;

其中快和慢的類型Link

class Link 
{ 
    int IData {get; set;} 
    Link Next {get; set;} 
}

B的。 他們是否指向相同的參考，即if (fast == slow)

謝謝。

來源

2011-12-02 parsh

'如果（快==慢）'是正確的檢查。 – Azodious

你只應該比較節點本身。畢竟，重複數據鏈接列表是合理的，沒有它實際上有一個循環。

我會電話他們的節點，而不是鏈接太。鏈接僅僅是從一個節點到下一個或前一個節點的參考 - 特別是，沒有與鏈接相關聯的數據，僅與節點有關。

來源

2011-12-02 07:13:42

所以你說的是類應該被命名爲： - Node {int IData {get;設置;}節點Next {get;組;}}。然後比較節點像; （快==慢）。謝謝，其實這篇文章有點讓我想到解決方案： - [鏈接]（http://navaneethkn.wordpress.com/2009/10/15/understanding-equality-and-object-comparison-in-net-framework/ ＃more-256） – parsh

@parsh：是的，就是這樣。 –

明白了。謝謝。 – parsh

希望這有助於...這可能是幼稚的，但它的工作原理...

using System; 

namespace CSharpTestTemplates 
{ 
class LinkedList 
{ 
    Node Head; 

    public class Node 
    { 
     public int value; 
     public Node NextNode; 

     public Node(int value) 
     { 
      this.value = value; 
     } 
    } 

    public LinkedList(Node head) 
    { 
     this.Head = head; 
    } 



    public Boolean hasLoop() 
    { 
     Node tempNode = Head; 
     Node tempNode1 = Head.NextNode; 
     while(tempNode!=null && tempNode1!=null){ 
      if(tempNode.Equals(tempNode1)){ 
       return true; 
      } 

      if ((tempNode1.NextNode != null) && (tempNode.NextNode != null)) 
      { 
       tempNode1 = tempNode1.NextNode.NextNode; 
       tempNode = tempNode.NextNode; 
      } 
      else 
      { 
       return false; 
      } 
     } 

     return false; 
    } 

    public static void Main() 
    { 
     Node head = new Node(1); 
     LinkedList ll = new LinkedList(head); 

     Node node2 = new Node(2); 
     Node node3 = new Node(3); 
     Node node4 = new Node(4); 
     Node node5 = new Node(5); 
     Node node6 = new Node(6); 

     head.NextNode = node2; 
     node2.NextNode = node3; 
     node3.NextNode = node4; 
     node4.NextNode = node5; 
     node5.NextNode = node6; 
     node6.NextNode = null; 

     Console.WriteLine(ll.hasLoop()); 
     Console.Read(); 
    } 
    } 
}

來源

2013-07-12 20:03:57 Som

使用C＃在鏈表中循環檢測

回答

相關問題