[Leetcode] Intersection of Two Linked Lists

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

begin to intersect at node c1.

Notes:

• If the two linked lists have no intersection at all, return null.
• The linked lists must retain their original structure after the function returns.
• You may assume there are no cycles anywhere in the entire linked structure.
• Your code should preferably run in O(n) time and use only O(1) memory.

The first method is like find the LCA of two nodes with parent pointer. We make the two nodes have the same "depth" and then look forward to see if there is a common node.

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null)
            return null; // corner case
        ListNode tempA = headA, tempB = headB;
        int lenA = 0, lenB = 0;
        // find the lenght of the two list
        while(tempA != null) {
            lenA++;
            tempA = tempA.next;
        }
        while(tempB != null) {
            lenB++;
            tempB = tempB.next;
        }
        tempA = headA;
        tempB = headB;
        // turncate the longer list
        if(lenA > lenB) {
            while(lenA > lenB) {
                lenA--;
                tempA = tempA.next;
            }
        }
        else if(lenA < lenB) {
            while(lenA < lenB) {
                lenB--;
                tempB = tempB.next;
            }
        }
        // find the first common listnode in the two list if exist
        while(tempA != null && tempB != null) {
            if(tempA == tempB)
                return tempA;
            tempA = tempA.next;
            tempB = tempB.next;
        }
        return null;
    }

The time complexity is O(m+n) and space complexity is O(1).
Another method is to create a cycle by hand. We link A's tail to its head, then if there indeed is a intersection node, there would be a cycle and the node would be the start point where the cycle begin. So we could use the same method for the single linked list. Remember to recover the two list to their original structure. The time complexity and space complexity is the same with the prior one.

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null)
            return null; // corner case
        ListNode tail = headA;
        // find the tail of A and link it to head
        while(tail.next != null)
            tail = tail.next;
        tail.next = headA;
        // B is now a single linked list with circle or not
        if(headB == null || headB.next == null) {
            tail.next = null;
            return null;
        }
        ListNode slow = headB, fast = headB;
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast)
                break;
        }
        // check if there is circle
        if(fast == null || fast.next == null) {
            tail.next = null;
            return null;
        }
        fast = headB;
        while(slow != fast) {
            fast = fast.next;
            slow = slow.next;
        } 
        // recover to original structure
        tail.next = null;
        return slow;
    }