题解 | #判断链表中是否有环#

秒懂【环形链表判断】！超清晰图解一步步拆解。

1.思路

如下图所示，链表1不存在环（最后一个节点指向Null），而链表2存在环（最后一个节点的指针域指向了第二个节点）。

判断链表是否存在环有个小技巧：快慢指针法。定义2个指针变量（即快慢指针），初始化时快慢指针都指向头节点，每次快指针每次移动 2 个节点，慢指针每次移动 1 个节点。如果 快指针指向的节点为null或者快指针指向节点的下一个节点为空，则链表没有环；如果快慢指针相遇则有环。

假如存在以下环链表，如下图所示：

判断链表是否有环步骤如下：

第一步：定义快慢指针。

第二步：移动快慢指针。

快指针fast移动2个节点，指向0节点；慢指针slow移动1个节点，指向2节点。

快指针fast再移动两个节点，这时会指向节点2；慢指针slow移动1个节点，指向0节点。

快指针fast再移动两个节点，这时会指向节点-4；慢指针slow移动1个节点，也指向-4节点。此时快慢指向都指向-4节点，则链表存在环。

如果文字描述的不太清楚，你可以参考视频的详细讲解：B站@好易学数据结构

2.代码

2.1 Pthon代码

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        # write code here
        if head is None:
            return False

        # 1. 定义快慢指针
        fast = head
        slow = head

        # 2.移动快慢指针
        while fast is not None and fast.next is not None:
            fast = fast.next.next  # 快指针每次移动2个节点（快指针每次走2步）
            slow = slow.next  # 慢指针每次移动1个节点（慢指针每次走一步）
            if fast == slow:
                return True  # 快慢指针相遇，有环
        # 快指针对应的节点为null  或者 快指针对应节点的下一个节点为null，则没有环
        return False

2.2 Java代码

public static class Solution {
        /**
         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
         *
         * @param head ListNode类
         * @return boolean
         */
        public boolean hasCycle(ListNode head) {
            // write code here
            if (head == null) {
                return false;
            }
            // 1. 定义快慢指针
            ListNode fast = head;
            ListNode slow = head;

            // 2. 移动快慢指针
            while (fast != null && fast.next != null) {
                fast = fast.next.next; //快指针每次移动2个节点（快指针每次走2步）
                slow = slow.next; //慢指针每次移动1个节点（慢指针每次走一步）
                if (slow == fast) {
                    return true;
                }
            }
            //快指针对应的节点为null 或者 快指针对应节点的下一个节点为null，则没有环
            return false;
        }
    }

2.3 Go代码

func hasCycle(head *ListNode) bool {
	// write code here
	if head == nil {
		return false
	}
	// 1. 定义快慢指针
	slow := head
	fast := head
	// 2. 移动快慢指针
	for fast != nil && fast.Next != nil {
		fast = fast.Next.Next //快指针每次移动2个节点（快指针每次走2步）
		slow = slow.Next      //慢指针每次移动1个节点（慢指针每次走一步）
		if fast == slow {
			return true
		}
	}
	//快指针对应的节点为null 或者 快指针对应节点的下一个节点为null，则没有环
	return false
}

如果上面的代码理解的不是很清楚，你可以参考视频的详细讲解：B站@好易学数据结构