141. Linked List Cycle

yPhantom 2019年10月14日 25次浏览

快慢指针 链表

2019-9-28: 忘记对slow和fast是否为null值进行判断。

题意让找出一条链表中是否有“圈”。简单利用快慢指针遍历即可。

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

上面是自己的写法,但是会容易导致空指针异常。

Discuss中的解法:

public boolean hasCycle(ListNode head) {
    if(head==null) return false;
    ListNode walker = head;
    ListNode runner = head;
    while(runner.next!=null && runner.next.next!=null) {
        walker = walker.next;
        runner = runner.next.next;
        if(walker==runner) return true;
    }
    return false;
}

出错的原因在于while的循环条件没有判断清楚。

先判断将要遍历节点是否存在,再进行赋值比较是最为科学的。


仔细改了下,这样应该是最精简的:

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