【力扣】141和142环形链表

141.环形链表

法一：快慢指针

思路：

用两个指针slow,fast,后者能比前者多走一步路，那判断是不是有环，只需要判断是否会相遇。

就是有一个能比乌龟跑2倍快的兔子，两小只都在有环的路上跑，那是不是肯定会相遇。

嗯，对！

代码：

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
       //快慢指针，参考物理上面的，二者是肯定会相遇的，这个根本就不用想
       if(head==null||head.next==null){
           return false;
       }
       ListNode slow=head;
       ListNode fast=head.next;
       while(slow!=fast){
           if(fast==null||fast.next==null){
               return false;
           }
           slow=slow.next;
           fast=fast.next.next;
       }
       return true;
    }
}

法二：哈希表

思路：

就是把之前走过的路标记一下，这里可以用哈希表set，set集合中是不允许有重复元素的。然后当重复结点出现的时候,就说明有环了。代码如下：

代码：

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        Set<ListNode> seen=new HashSet<ListNode>();
        while(head!=null){
            if(!seen.add(head)){
                return true;
            }
            head=head.next;
        }
        return false;
    }
}

142.环形链表II

?这道题可以借鉴141.环形链表的解法，不过是用哈希表的没多少改动，但是用快慢指针的话那就需要额外注意了。

在这里的话我犯了一个错误，用快慢指针法的时候我认为两指针相遇的结点就是该链表开始入环的第一个节点。还有就是当head=[-1, -7, 7, -4, 19, 6, -9, -5, -2, -5] ,p=9时就错误的认为两个-5就是相同的。

题解：

设一个情景，方便理解。有个乌龟和兔子，兔子腿长，当然就跑的比较快，这里我规定其速度为乌龟的两倍。它俩在一个有环的地方相遇。看下图，红点的地方是相遇点，然后我们可以得出乌龟走的路是X+Y，兔子的是X+Y+N*(Y+Z)，这个能看懂吧，然后两者的关系是2*(X+Y)=X+Y+N*(Y+Z)，因为速度是2倍关系。然后化简最后就是X=(n-1)(Y+Z)+Z。好，这里的话。我们这样来理解。当n等于1时，X=Z，意味着只要用个命运之手将爬到相遇点的乌龟放到原点（多多少少有点残忍），然后再将兔子限速为乌龟的速度，这样二者必将会在目的点相遇，这个时候我们只需要返回即可。那么当n>1时，那也没关系，这就说明x的确实有点长，兔子只需要继续保持着龟速前进即可。图有点丑，见谅见谅！

?代码如下啦：

（参考官方）

码一：快慢指针

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head==null) return null;
        ListNode slow=head,fast=head;
        while(fast!=null){
            slow=slow.next;
            if(fast.next!=null){
                fast=fast.next.next;
            }else{
                return null;
            }
            if(fast==slow){
                ListNode ptr=head;
                while(ptr!=slow){
                    ptr=ptr.next;
                    slow=slow.next;
                }
                return ptr;
            }
        }
        return null;
    }
}

码二：哈希表

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        Set<ListNode> seen=new HashSet<ListNode>();
        while(head!=null){
            if(!seen.add(head)){
                return head;
            }
            head=head.next;
        }
        return null;
    }
}

其实还挺简单的，主要就是要理解！

好了，刷题快乐哟~