07、环形链表

题目描述

环形链表

下面我们再来了解一种双指针，我们称之为快慢指针，顾名思义一个指针速度快，一个指针速度慢。

给定一个链表，判断链表中是否有环。pos 代表环的入口，若为-1，则代表无环。

如果链表中存在环，则返回 true 。否则，返回 false 。

示例 1：

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

题目解析

题目很容易理解，让我们判断链表中是否有环，我们只需通过我们的快慢指针即可，我们试想一下，如果链表中有环的话，一个速度快的指针和一个速度慢的指针在环中运动的话，若干圈后快指针肯定可以追上慢指针的。这是一定的。

好啦，做题思路已经有了，让我们一起看一下代码的执行过程吧。

动画模拟

代码

Java Code:

public class Solution {
    public boolean hasCycle(ListNode head) {
         ListNode fast = head;
         ListNode low = head;
         while (fast != null && fast.next != null) {
             fast = fast.next.next;
             low = low.next;
             if (fast == low) {
                 return true;
             }
         }
         return false;
    }
}

C++ Code:

class Solution {
public:
    bool hasCycle(ListNode *head) {
         ListNode * fast = head;
         ListNode * slow = head;
         while (fast != nullptr && fast->next != nullptr) {
             fast = fast->next->next;
             slow = slow->next;
             if (fast == slow) {
                 return true;
             }
         }
         return false;
    }
};

JS Code:

var hasCycle = function (head) {
  let fast = head;
  let slow = head;
  while (fast && fast.next) {
    fast = fast.next.next;
    slow = slow.next;
    if (fast === slow) {
      return true;
    }
  }
  return false;
};

Python Code:

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        fast = head
        slow = head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                return True
        return False

Swift Code：

class Solution {
    func hasCycle(_ head: ListNode?) -> Bool {
        var fast = head, slow = head
        while fast != nil && fast?.next != nil {
            fast = fast?.next?.next
            slow = slow?.next
            if fast === slow {
                return true
            }
        }
        return false
    }
}

Go Code:

func hasCycle(head *ListNode) bool {
    if head == nil { return false }
    s, f := head, head
    for f != nil && f.Next != nil {
        s = s.Next
        f = f.Next.Next
        if s == f {
            return true
        }
    }
    return false
}