分享程序员开发的那些事...
更新时间：2022-09-14 09:07:07
一，问题描述
给定一个单链表，单链表中有环，请找出这个环的入口结点。比如，如下单链表：
入口结点是，结点4.
二，实现思路
如果仅仅是寻找入口结点，可以更改结点元素的值的话，只需要扫描一遍就可以找到入口结点了。
比如，假设所有的结点值都是正数，从头开始，那么在扫描过程中，将扫描的结点的值与 0 比较，如果不是0，则置为0；如果是0，则说明这个结点就是入口结点。
这种方式非常简单高效，只需要扫描一遍链表就可以找到入口结点了。缺点是：它修改了链表中结点的值。
如果不允许修改结点的值，处理相对复杂一点。
1）假设单链表中的环有N个结点（在上面的示例图中环有3个结点），可以设置两个指针p1 和 p2，初始时，p1 和 p2 都指向表头，指针p1 先在 链表中移动 N 步，然后 p1 和 p2 再以相同的速度向前移动(每次向前移动一个结点)，当p2指向环的入口结点时，p1已经沿着环走了一圈又回到了入口结点。也即：当两个结点相遇时，相遇时共同指向的这个结点就是环的入口结点。
2）那么，现在的问题变成了：如何找出单链表中的环包含几个结点？[参考：钟表的分针是如何追上时针的？]
比如，下面的单链表中的环包含了3个结点。
设置两个指针 q1 和 q2，让 q1 移动的速度是 q2 的两倍，即：q1 每次移动两个结点，q2 每次移动 一个结点。
初始时，q1 和 q2 都指向头结点，然后 q1 和 q2 开始移动，当 q1 再次 与 q2 相遇时，它们一定是在环中的某个结点上相遇的。
然后，再固定 q1 不动，让 q2 遍历链表，并记录它遍历的结点个数。当 q2 再次与q1相遇时，它所遍历的结点个数就是环中结点的个数了。
三，代码实现
上面用到了单链表，因此得有结点的定义，这里结点类以内部类实现。
public class EntryNode { private class Node{ int ele; Node next; public Node(int ele) { this.ele = ele; next = null; } } private Node head;//头结点 //other code.....
首先，得构造一个带环的单链表。通过insert()方法和 makeEntry()方法来构造带环的单链表。
//采用头插法,插入结点 public void insert(int ele){ Node newNode = new Node(ele); if(head == null) head = newNode; else { newNode.next = head.next; head.next = newNode; } }
insert()采用“头插法”方式将结点插入到链表中
/*ele 就是入口结点的值 * 构造一个带环的链表.如果 ele 不属于链表中的值,则抛出IllegalArgumentException * point 用来遍历链表,prePoint记录遍历链表时的前驱结点. * 当 point.ele == ele时, 指定 当前 point 指向的结点作为 入口 结点 * * 然后 point 继续遍历,直到遍历到尾结点. 然后最终由prePoint记录尾结点, 并将尾结点的next指针指向入口结点 */ public void makeEntry(int ele){ //assume ele in Node List Node point,prePoint; prePoint = point = head; Node entry = null; while(point != null) { if(point.ele == ele) entry = point;//entry is circle's first node(entry node) prePoint = point; point = point.next; } if(entry == null)// ele does not in list, can not make a circle throw new IllegalArgumentException(ele + " does not in list, can not make a circle"); prePoint.next = entry;//prePoint is last node }
makeEntry()方法，负责让单链表的表尾结点 的next指针 指向 链表中的某个结点，从而构成了一个环。
findEntry()方法找出入口结点的值。整个完整代码实现如下：
public class EntryNode { private class Node{ int ele; Node next; public Node(int ele) { this.ele = ele; next = null; } } private Node head;//头结点 //采用头插法,插入结点 public void insert(int ele){ Node newNode = new Node(ele); if(head == null) head = newNode; else { newNode.next = head.next; head.next = newNode; } } /*ele 就是入口结点的值 * 构造一个带环的链表.如果 ele 不属于链表中的值,则抛出IllegalArgumentException * point 用来遍历链表,prePoint记录遍历链表时的前驱结点. * 当 point.ele == ele时, 指定 当前 point 指向的结点作为 入口 结点 * * 然后 point 继续遍历,直到遍历到尾结点. 然后最终由prePoint记录尾结点, 并将尾结点的next指针指向入口结点 */ public void makeEntry(int ele){ //assume ele in Node List Node point,prePoint; prePoint = point = head; Node entry = null; while(point != null) { if(point.ele == ele) entry = point;//entry is circle's first node(entry node) prePoint = point; point = point.next; } if(entry == null)// ele does not in list, can not make a circle throw new IllegalArgumentException(ele + " does not in list, can not make a circle"); prePoint.next = entry;//prePoint is last node } public int findEntry(){ if(head == null) throw new IllegalArgumentException(); //如果链表中只有一个节点,不需要求解环中节点的个数 if(head.next == head) return head.ele; int circleNumber = circleNumbers(); assert circleNumber > 0; Node next_k, current; next_k = current = head; for(int i = 1; i <= circleNumber; i++) next_k = next_k.next; while(current != next_k) { current = current.next; next_k = next_k.next; } return next_k.ele; } private int circleNumbers(){ Node pre,next; pre = next = head; next = next.next.next;//next 先走2步 //每个节点往后移 while(pre != next) { pre = pre.next; next = next.next.next; } //now pre and next pointer all point same node int circleNumber = 0; circleNumber++; next = next.next;//next forward one step while(next != pre) { circleNumber++; next = next.next; } return circleNumber; } //hapjin test public static void main(String[] args) { EntryNode entryNode = new EntryNode(); int[] eles = {1，2，3，4，5，6}; for (int ele : eles) { entryNode.insert(ele); } entryNode.makeEntry(4);//至此,构造完了一个带环的链表 System.out.println("入口结点的值为: " + entryNode.findEntry()); } }
本文转自hapjin博客园博客，原文链接：http://www.cnblogs.com/hapjin/，如需转载请自行联系原作者