判断 链表 成环(快慢指针)

判断链表成环,通常使用的方法是快慢指针法,一个快指针每次向后指两步,一个慢指针向后指一步,则当快指针与慢指针相当时,链表成环.

可以将快慢指针想象成两个运动员苏炳添和你,苏炳添跑得快,你跑的慢,因此在操场这种环形跑道上时,苏炳添早晚会与你相遇,但如果是直线跑道,则不会相遇.

快指针,和慢指针都指向1

快指针先指向2,再指向3,慢指针指向2

快指针指向4,再指向3,慢指针指向3,此时快指针与慢指针相遇,说明成环.

十分重要的是,当这个链表不成环时,快指针会一直走到链表的尾部,若再走则会产生空指针(NullPoint),因此要判断快指针quick!=null并且quick.next!=null.

java实现

public class Solution {

    public boolean hasCycle(ListNode head) {

        ==//声明两个节点从头开始遍历节点==

        ListNode quick = head;

        ListNode slow = head;

        //当快指针能够走到头表示无环

        while(quick!=null&&quick.next!=null){

            quick = quick.next.next;

            slow = slow.next;

            if(quick==slow){

                return true;

            }

        }     

    return false;

    }

    }

在硬件中的表示其中左是栈,右是堆