黑马程序员技术交流社区

标题: 【黑马程序员西安校区】带环链表的相关问题 [打印本页]
作者: 就业高冷派    时间: 2017-11-10 14:47
标题: 【黑马程序员西安校区】带环链表的相关问题
首先，关于单链表中的环，一般涉及到一下问题：
1. 给一个单链表，判断其中是否有环的存在；
2. 如果存在环，找出环的入口点；
3. 如果存在环，求出环上节点的个数；
下面，我将针对上面这三个问题一一给出解释和相应的代码。
1. 判断时候有环（链表头指针为head）
对于这个问题我们可以采用“快慢指针”的方法。就是有两个指针fast和slow，开始的时候两个指针都指向链表头head，然后在每一步
操作中slow向前走一步即：slow = slow.next，而fast每一步向前两步即：fast = fast.next.next。
由于fast要比slow移动的快，如果有环，fast一定会先进入环，而slow后进入环。当两个指针都进入环之后，经过一定步的操作之后
二者一定能够在环上相遇，并且此时slow还没有绕环一圈，也就是说一定是在slow走完第一圈之前相遇。证明可以看下图：
当slow刚进入环时每个指针可能处于上面的情况，接下来slow和fast分别向前走即：

file:///D:/%E7%94%A8%E6%88%B7%E7%9B%AE%E5%BD%95/documents/tencent%20files/3221227885/filerecv/media/15096873549553/15096878622007.jpg
当slow刚进入环时每个指针可能处于上面的情况，接下来slow和fast分别向前走即：
if(fast!=null && fast.next!=null){     fast = fast.next.next;     slow = slow.next;}
也就是说，slow每次向前走一步，fast向前追了两步，因此每一步操作后fast到slow的距离缩短了1步，这样继续下去就会使得
两者之间的距离逐渐缩小：...、5、4、3、2、1、0 -> 相遇。又因为在同一个环中fast和slow之间的距离不会大于换的长度，因此
到二者相遇的时候slow一定还没有走完一周（或者正好走完以后，这种情况出现在开始的时候fast和slow都在环的入口处）。
下面给出问题1的完整代码：
/** * Definition for ListNode. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int val) { *         this.val = val; *         this.next = null; *     } * } */ public class Solution {    /**     * @param head: The first node of linked list.     * @return: True if it has a cycle, or false     */    public boolean hasCycle(ListNode head) {          // write your code here        ListNode fast = head;        ListNode slow = head;        while(fast!=null && fast.next!=null){            fast = fast.next.next;            slow = slow.next;            if(fast == slow){                return true;            }        }        return false;    }}2. 找出环的入口点：
我结合着下图讲解一下：

file:///D:/%E7%94%A8%E6%88%B7%E7%9B%AE%E5%BD%95/documents/tencent%20files/3221227885/filerecv/media/15096873549553/15096883613503.jpg
从上面的分析知道，当fast和slow相遇时，slow还没有走完链表，假设fast已经在环内循环了n(1<= n)圈。假设slow走了s步，则fast走了2s步，又由于
fast走过的步数 = s + n*r（s + 在环上多走的n圈），则有下面的等式：
2*s = s + n * r ; (1)
=> s = n*r (2)
如果假设整个链表的长度是L，入口和相遇点的距离是x（如上图所示），起点到入口点的距离是a(如上图所示)，则有：
a + x = s = n * r; (3) 由（2）推出
a + x = (n - 1) * r + r = (n - 1) * r + (L - a) (4) 由环的长度 = 链表总长度 - 起点到入口点的距离求出
a = (n - 1) * r + (L -a -x) (5)
集合式子（5）以及上图我们可以看出，从链表起点head开始到入口点的距离a,与从slow和fast的相遇点（如图）到入口点的距离相等。
因此我们就可以分别用一个指针（ptr1, prt2），同时从head与slow和fast的相遇点出发，每一次操作走一步，直到ptr1 == ptr2，此时的位置也就是入口点！
到此第二个问题也已经解决,代码如下：
/** * Definition for ListNode. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int val) { *         this.val = val; *         this.next = null; *     } * } */ public class Solution {    /**     * @param head: The first node of linked list.     * @return: The node where the cycle begins.      *           if there is no cycle, return null     */    public ListNode detectCycle(ListNode head) {          ListNode fast = head;        ListNode slow = head;        boolean hasCycle = false;        while(fast!=null && fast.next!=null){            fast = fast.next.next;            slow = slow.next;            if(fast == slow){                hasCycle = true;                break;            }        }        if(hasCycle == true){            slow = head;            while(slow!=fast){                slow = slow.next;                fast = fast.next;            }            return slow;        }        return null;    }}3. 如果存在环，求环上节点的个数：
对于这个问题，我这里有两个思路（肯定还有其它跟好的办法）：
思路1：记录下相遇节点存入临时变量tempPtr，然后让slow(或者fast，都一样)继续向前走slow = slow.next；一直到slow == tempPtr; 此时经过的步数就是环上节点的个数；
思路2： 从相遇点开始slow和fast继续按照原来的方式向前走slow = slow. next; fast = fast. next. next；直到二者再次相遇，此时经过的步数就是环上节点的个数 。
第一种思路很简单，其实就是一次遍历链表的环，从而统计出点的个数，没有什么可以详细解释的了。
对于第二种思路，我们可以这样想，结合上面的分析，fast和slow没一次操作都会使得两者之间的距离较少1。我们可以把两者相遇的时候看做两者之间的距离正好是整个环的长度r。因此，当再次相遇的时候所经过的步数正好是环上节点的数目。
由于这两种思路都比较简单，代码也很容易实现，这里就不给出了。






欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2