List Cycle

Intersection of two linked list

we don't care about the "value" of difference, we just want to make sure two pointers reach the intersection node at the same time. We can use two iterations to do that. In the first iteration, we will reset the pointer of one linkedlist to the head of another linkedlist after it reaches the tail node. In the second iteration, we will move two pointers until they points to the same node. Our operations in first iteration will help us counteract the difference. So if two linkedlist intersects, the meeting point in second iteration must be the intersection point. If the two linked lists have no intersection at all, then the meeting pointer in second iteration must be the tail node of both lists, which is null.

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

    if (headA == null || headB == null) return null;

    // we don't need to know the length of two lists and diff.. so just use two iterations 
    ListNode curA = headA, curB = headB;
    while (curA != curB) {
        // two senoria worth noting ..
        // 1. there exists intersection between two lists
        // 2. no intersection 
        curA = curA == null ? headB : curA.next;
        curB = curB == null ? headA : curB.next;
    }

    return curA;
}

Linked List Cycle

the simple method is to use hash table to check if we have visited the node before.

We go through each node one by one and record each node's reference (or memory address) in a hash table. If the current node is null, we have reached the end of the list and it must not be cyclic. If current node’s reference is in the hash table, then return true.

public class Solution {
    public boolean hasCycle(ListNode head) {
        Set<ListNode> set = new HashSet<>();
        while (head != null) {
            if (set.contains(head)) {
                return true;
            } else {
                set.add(head);
            }
            head = head.next;
        }
        return false;
    }
}

time complexity is O(n) and space complexity is O(n)

another method is to use two pointers with different moving speed, if two pointers meet finally, we can say there exists a cycle in it. If there is no cycle in the list, the fast pointer will eventually reach the end and we can return false in this case. Now consider a cyclic list and imagine the slow and fast pointers are two runners racing around a circle track. The fast runner will eventually meet the slow runner. For different cases, we have the same result.

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

        return false;
    }
}

time complexity is O(n) and space complexity is O(1)

follow up? determine the meeting point

The algorithm is separated into two distinct phases. In the first phase, it determines whether a cycle is present in the list. If no cycle is present, it returns null immediately, as it is impossible to find the entrance to a nonexistant cycle. Otherwise, it uses the located "intersection node" to find the entrance to the cycle.

public ListNode detectCycle(ListNode head) {
    if (head == null) return head;

    ListNode fast = head, slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        if (fast == slow) {
            break;
        }
    }

    if (fast == null || fast.next == null) {
        return null;
    }

    fast = head;
    while (fast != slow) {
        fast = fast.next;
        slow = slow.next;
    }

    return slow;
}