Linked list related

• reverse a linked list

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

    ListNode newHead = null;
    while (head != null) {
        ListNode temp = head.next;
        head.next = newHead;
        newHead = head;
        head = temp;
    }
    return newHead;
}

• detect loop on a linked list

// we can use a slow(1 step) and a fast pointer(2 step) to detect loop
// because it's like finding LCM of 1 and 2, if there is a loop
// two pointers will meet eventually
public boolean hasCycle(ListNode head) {
    if (head == null) {
        return false;
    }

    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) {  // null detection defer to next loop
        fast = fast.next.next;
        slow = slow.next;
        if (slow == fast)
            return true;
    }
    return false;
}

detect loop and find the intersection

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

    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) {  // null detection defer to next loop
        fast = fast.next.next;
        slow = slow.next;
        if (slow == fast)
            break;
    }

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

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

Code pattern

偵測環: slow + fast, fast null 偵測留給下個 loop

找到交叉點: 偵測環 + 一起走