141. Linked List Cycle

Question

141. Linked List Cycle

Solution

题目大意：给一个链表，判断是否存在循环，最好不要使用额外空间

思路：定义一个假节点fakeNext，遍历这个链表，判断该节点的next与假节点是否相等，如果不等为该节点的next赋值成fakeNext

Java实现：

public boolean hasCycle(ListNode head) {
    // check if head null
    if (head == null) return false;

    ListNode cur = head;
    ListNode fakeNext = new ListNode(0); // define a fake next
    while (cur.next != null) {
        if (cur.next == fakeNext) {
            return true;
        } else {
            ListNode tmp = cur;
            cur = cur.next;
            tmp.next = fakeNext;
        }
    }
    return false;
}