算法6.環(huán)形鏈表

這個(gè)題曾經(jīng)被問到過，當(dāng)我準(zhǔn)備進(jìn)行邏輯推理的時(shí)候，直接被打斷了，其實(shí)算法題真的背過就好了，或者把第一印象記住，之后一旦被問到，稍微摸一下腦瓜子，然后把自己背過的東西假裝很順利地推導(dǎo)出來，這其實(shí)才是面試官想要的東西。

給定一個(gè)鏈表，判斷鏈表中是否有環(huán)。

快慢指針解法：一般提到這個(gè)鏈表的算法題，快慢指針這個(gè)概念我們一定要時(shí)刻牢記，不只是在這個(gè)地方有用，曾經(jīng)還有一道面試題也用過這個(gè)概念，不過我現(xiàn)在一時(shí)半會(huì)記不起來了。顯而易見，在一個(gè)環(huán)里面，跑的快的遲早能夠再遇上跑得慢的。

代碼如下：

/** * @author Ted * @version 1.0 * @date 2021/10/16 17:54 */public class CircleListNode {

    public static void main(String[] args) {
        CircleListNode circleListNode = new CircleListNode();        ListNode head = new ListNode(8);        ListNode node2 = new ListNode(3);        head.next = node2;        ListNode node3 = new ListNode(3);        node2.next = node3;        ListNode node4 = new ListNode(3);        node3.next = node4;        ListNode node5 = new ListNode(3);        node4.next = node5;        ListNode node6 = new ListNode(3);        node5.next = node6;        //尾指針指向node3 產(chǎn)生環(huán)        node6.next = node3;
        boolean b = circleListNode.hasCycle(head);        System.out.println(b);    }
    public boolean hasCycle(ListNode head) {        if (head == null || head.next == null) {            return false;        }        ListNode slow = head;        ListNode fast = head.next;        while (slow != fast) {            if (fast == null || fast.next == null) {                return false;            }            slow = slow.next;            fast = fast.next.next;        }        return true;    }
}
class ListNode{    public int val;    public ListNode next;

    public ListNode(int val){        this.val = val;    }}