Leetcode#141,#142_环形链表(剑指Offer#23)

剑指offerLeetCode

Contents

Leetcode #141 环形链表
题目
思路分析
双指针法
解答
Leetcode #142 环形链表II
题目
思路分析
解答
剑指Offer#23 链表中环的入口节点

剑指Offer#23,Leetcode上面没有，是在牛客上做的，链接：链表中环的入口结点。

leetcode#141,#142题和此题类似，所以连同这两题一起做。

Leetcode #141 环形链表

题目

给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。

思路分析

双指针法

设置一快一慢两个指针，慢指针每次走1步，快指针每次走2步。两个指针同时开始遍历链表。
指针进入环形部分后，两个指针的运动过程类似于我们学过的追及问题。两个指针都在绕圈，一个快，一个慢，那么快指针必然会追上慢指针。
也就是，当快指针和慢指针相遇时，说明相遇的位置就是环里的一个节点，也就证明链表有环。
否则，快指针必定先遇到null,这时直接证明链表没有环（有环就不可能遇到null，而是可以一直绕着环移动）。
特殊输入

输入空链表，直接返回false。
只有一个节点（有环或五环）的情况，可以代入代码验证。

问题：
快指针每次走2步，慢指针每次走1步，那么会不会出现刚好快指针超过慢指针1步，二者刚好错过，不能相遇情况呢？
解答：
不会出现这种情况，因为如果快指针刚好超过慢指针1步，那说明上一轮迭代时是相遇的。其他情况也类似：

如果快指针落后慢指针1步，那么下一轮迭代就会相遇。
如果快指针落后慢指针2步，那么下两轮迭代就会相遇。
...

总结规律就是，快指针和慢指针的运动是相对的，每次快指针相对慢指针靠近1步，所以不会出现因为快指针走2步而错过相遇点的情况。

解答

public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head == null) return false;
        ListNode fast = head.next;
        ListNode slow = head;
        while(fast != slow){//fast和slow指针相遇时，循环结束，证明有环
            //因为fast指针更新的时候，需要访问fast.next.next,所以fast.next不可以是null
            if(fast == null || fast.next == null) return false;
            slow = slow.next;//slow前进1步
            fast = fast.next.next;//fast前进2步
        }
        return true;     
    }
}

Leetcode #142 环形链表II

题目

给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。
说明：不允许修改给定的链表。

思路分析

这题与剑指Offer#24相同。
整个问题可以分解为三个子问题：

寻找环里的其中一个节点（即上述的Leetcode#141题），如果找不到，说明没有环，返回false。
- 快慢指针法，相遇节点记为meetNode
计算环的周长
- 快慢指针在meetNode处相遇，这时慢指针不动，快指针向后遍历，直到遇到慢指针，这个过程快指针走过的步数就是环的周长，记作n。
寻找环的入口节点
- 重置快慢指针，都指向链表头节点
- 快指针先走n步，然后快慢指针一起走，每次走一步
- 由于快指针多走了n，也就是比慢指针多走了环的一圈，所以当慢指针到达环入口节点时，快指针也刚好走完一圈，回到入口节点。快慢指针相遇处就是环入口节点。

解答

public class Solution {
    //两个指针是类内公用的
    ListNode fast;
    ListNode slow;
    public ListNode detectCycle(ListNode head) {
        ListNode meetNode = findMeetNode(head);
        if(meetNode == null) return null;//无环
        int cycleNum = countCycleNum(meetNode);
        fast = head;
        slow = head;
        for(int i = 1; i <= cycleNum;i++){//fast先走环周长那么多步
            fast = fast.next;
        }
        while(fast != slow){//同时移动，直到相遇
            fast = fast.next;
            slow = slow.next;
        }
        return fast;       
    }
    //寻找相遇节点，同141题
    public ListNode findMeetNode(ListNode head){
        if(head == null) return null;//没有环，返回null
        slow = head;
        fast = head.next;
        while(fast != slow){
            if(fast == null || fast.next == null) return null;//没有环，返回null
            slow = slow.next;
            fast = fast.next.next;
        }
        return fast;   
    }

    public int countCycleNum(ListNode meetNode){
        fast = fast.next;//fast先走一步,否则无法进入循环
        int cycleNum = 1;//由于已经走了一步，所以直接初始化为1
        while(fast != slow){
           fast = fast.next;
           cycleNum++;
        }
        return cycleNum;
    }
}

剑指Offer#23 链表中环的入口节点

链接：链表中环的入口结点
本题和leetcode 142一样，按照142题写法，修改下函数输入参数名，即可通过。