【LeetCode】[141] 环形链表-hashmap、递归、双指针

/*
 * @lc app=leetcode.cn id=141 lang=java
 *
 * [141] 环形链表
 */

// 给定一个链表，判断链表中是否有环。

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

// 输入：head = [3,2,0,-4], pos = 1
// 输出：true
// 解释：链表中有一个环，其尾部连接到第二个节点。
 

// 示例 2：

// 输入：head = [1,2], pos = 0
// 输出：true
// 解释：链表中有一个环，其尾部连接到第一个节点。


// 示例 3：

// 输入：head = [1], pos = -1
// 输出：false
// 解释：链表中没有环。

我的代码，用了hash表存储之前的链表地址，若后面出现重复的链表地址，则有环

//  Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}

class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null) return false;
        HashMap<ListNode, Integer> hashMap = new HashMap<ListNode, Integer>();
        hashMap.put(head, head.val);
        ListNode node = head;
        ListNode nextNode = node.next;
        while(nextNode != null) {
            if (hashMap.containsKey(nextNode)) {
                return true;
            } else {
                hashMap.put(nextNode, nextNode.val);
            }
            nextNode = nextNode.next;
        }
        return false;
    }
}

大佬的代码，用了递归思想

class HasCycleInLinkedList{
    public boolean hasCycle(ListNode head){
        if(head == null || head.next == null) return false;
        if(head.next == head) return true;
        ListNode nextNode = head.next; 
        head.next = head;
        boolean isCycle = hasCycle(nextNode);
        return isCycle;
    }
 }

双指针法

双指针在链表的操作中比较常见，应该作为一种常用的思路记住。还以上面的图为例，我们设置两个指针从head开始遍历，规定两个指针的前进速度不一样，分别称为快、慢指针，如下图所示，slow指针每次前进一个，fast指针每次前进两个节点。

因为fast指针每次前进两个，一定比slow指针先到达环的入口处。而当slow指针进入环的时候，fast指针已经经过了两个节点，如下图所示。这个时候，我们将这个过程想象成400m跑步的追及问题。如果存在环的话，因为fast指针速度更快，一定会追上slow指针。而如果fast指针没有追上slow指针，一定是因为链表不存在环

java代码实现双指针

 //双指针
 class HasCycle2{
    public boolean hasCycle(ListNode head){
        if(head == null || head.next == null) return false;
        ListNode pFast = head;
        ListNode pSlow = head;
        while (pFast != null && pFast.next != null) {
            pFast = pFast.next.next;
            pSlow = pSlow.next;
            if (pFast == pSlow) {
                return true;
            }
        }
        return false;
    }
 }