C#判断一个单链表是否有环及环长和环的入口点

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› Node.js›Node.js教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

1.为什么写这个随笔？

前几天参加一个电面，被问到这个问题，想总结一下。

2.为什么标题强调C#？

想在网上看看代码，却没找到C#版的，于是自己用C#实现一下。

一、解决问题的思路

1.一种比较耗空间的做法是，从头开始遍历链表，把每次访问到的结点存入一个集合（hashset）或字典（dictionary），如果发现某个结点已经被访问过了，就表示这个链表存在环，并且这个结点就是环的入口点。

空间复杂度为O(n)，时间复杂度为O(n)

2.追赶法：使用两个slow, fast指针从头开始扫描链表。指针slow 每次走1步，指针fast每次走2步。如果存在环，则指针slow、fast会相遇；如果不存在环，指针fast遇到NULL退出。

空间复杂度为O(1)，时间复杂度为O(n)

仅仅考虑代码实现方面第一种方法相对简单，所以下面用第二种方法来实现。

二、解析（追击相遇）

给出一个存在环的单链表：1,2,3,4,5,3,4,5...

用图表示出来：

然后按照追赶法的定义一步一步走：

从上图可以看出第四次和第七次快慢指针在节点4处相遇，7-4=3，正好是环的长度；

求出环的长度后，我们便可以求出入口点：

链表总长=5；

头结点到入口点的距离=链表总长-环长；即=5-3=2；

然后从头结点开始向下遍历，得到入口点3；

三、代码

1.单链表节点

 1 //单链表节点 
 2 class LinkNode<T>
 3     {
 4         public LinkNode<T> Next
 5         { get; set; }
 6         public T Data
 7         { get; set; }
 8         public LinkNode()
 9         {
10             Data = default(T);
11             Next = null;
12         }
13         public LinkNode(T val)
14         {
15             Data = val;
16             Next = null;
17         }
18         public LinkNode(T val,LinkNode<T> node)
19         {
20             Data = val;
21             Next = node;
22         }
23     }

2.单链表

  1     class DLinkedList<T>
  2     {
  3         public LinkNode<T> Head
  4         { get; set; }
  5         public int Length
  6         { get; set; }
  7         public DLinkedList()
  8         {
  9             Length = 0;
 10             Head = null;
 11         }
 12         public void Add(LinkNode<T> node)//插入节点
 13         {
 14             if (IsEmpty())
 15             {
 16                 Head = node;
 17                 Length++;
 18                 return;
 19             }
 20             else
 21             {
 22                 LinkNode<T> currentNode = Head;
 23                 while (currentNode.Next != null)
 24                 {
 25                     currentNode = currentNode.Next;
 26                 }
 27                 currentNode.Next = node;
 28                 Length++;
 29             }
 30         }
 31         public void Display()//显示链表
 32         {
 33             LinkNode<T> currentNode = Head;
 34             while (currentNode != null)
 35             {
 36                 Console.WriteLine(currentNode.Data);
 37                 currentNode = currentNode.Next;
 38             }
 39         }
 40         public int GetLength()//获取链表长度
 41         {
 42             return Length;
 43         }
 44         public bool IsEmpty()//判空
 45         {
 46             return Head == null ? true : false;
 47         }
 48         public bool HasCircle()//判断是否有环
 49         {
 50             LinkNode<T> slowNode = Head;
 51             LinkNode<T> fastNode = Head;//定义快慢节点，开始指向头结点
 52             bool result = false;
 53             int count = 0;
 54             int step = 0;
 55             while (slowNode.Next != null && fastNode.Next.Next != null)
 56             {
 57                 try
 58                 {
 59                     slowNode = slowNode.Next;//慢节点指向下一个
 60                     fastNode = fastNode.Next.Next;//快节点指向下一个节点的下一个节点
 61                 }
 62                 catch (NullReferenceException)
 63                 {
 64                     result = false;
 65                     break;
 66                 }
 67                 if (slowNode == fastNode && slowNode != Head && slowNode != null)
 68                 {
 69                     result = true;
 70                     Console.WriteLine($"The currentNode's Data is {slowNode.Data}");
 71                     count++;
 72                 }
 73                 if (count == 1)//第一次相遇
 74                     step++;//计步，获取环长
 75                 if (count == 2)//第二次相遇
 76                 {
 77                     Console.WriteLine($"Circle's length is {step}");
 78                     break;
 79                 }
 80             }
 81             GetPoint(step);
 82             return result;
 83         }
 84         public LinkNode<T> GetPoint(int circleLength)//获取相交点
 85         {
 86             int lineLength = Length -circleLength;
 87             int num = 1;
 88             LinkNode<T> currentNode = Head;
 89             while(currentNode.Next!=null)
 90             {
 91                 currentNode = currentNode.Next;
 92                 num++;
 93                 if(num==lineLength)
 94                 {
 95                     break;
 96                 }
 97             }
 98             Console.WriteLine($"The meet node's Data is {currentNode.Data}");
 99             return currentNode;
100         }
101     }

3.测试

 1 class Program
 2     {
 3         static void Main(string[] args)
 4         {
 5             DLinkedList<int> list = new DLinkedList<int>();
 6             LinkNode<int> tmp=null;
 7             for(int i =1;i<=10;i++)
 8             {
 9                 LinkNode<int> node = new LinkNode<int>(i);
10                 if (i == 4)
11                     tmp = node;
12                 list.Add(node);
13             }
14             list.Add(tmp);
15             Console.WriteLine(list.HasCircle());
16             Console.ReadKey();
17         }
18     }