leetcode解題：(Easy) 141. Linked List Cycle

題目：https://leetcode.com/problems/linked-list-cycle/

描述：輸入一個鏈結串列的head，判斷該鏈結串列是否存在指標迴圈(cycle)

解題思路：使用Fast-slow pointer法，類似時鐘上不同速度的指針一定會在某個地方重疊，利用2個前進速度不同的指標，如果鏈結串列中有迴圈2個指標一定會在某個時間點重疊。

程式碼：

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head == null || head.next == null) return false;

        ListNode node1 = head;
        ListNode node2 = head.next;
        
        while(node2 != null && node2.next != null) {
            if(node1 == node2) return true;
            node1 = node1.next;
            node2 = node2.next.next;
        }

        return false;
    }
}

時間複雜度：O(n)
空間複雜度：O(1)

tags: leetcode easy linked list two pointer