Thursday, December 11, 2014

Intersection of Two LinkedList LeetCode (Important)


1. Find the length of each list
2. Scan from the same length of the short list in the longer list.

It should be O(n) time and O(1) space.
It is not easy for me :(

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
       
        //Get the length 0f List A
        int indexA = 0;
        ListNode tempA = headA;
        while (tempA != null) {
            tempA = tempA.next;
            indexA++;
        }
       
        //Get the length of List B
        int indexB = 0;
        ListNode tempB = headB;
        while (tempB != null) {
            tempB = tempB.next;
            indexB++;
        }
       
        //Two pointers
       
        ListNode longNode = (indexA > indexB) ? headA : headB;
        ListNode shortNode = (longNode == headA) ? headB : headA;
        int diff = Math.abs(indexA - indexB);
        while (diff > 0) {
            longNode = longNode.next;
            diff--;
        }
       
        while (longNode != null) {
            if (longNode.val == shortNode.val) {
                return longNode;
            }
            longNode = longNode.next;
            shortNode = shortNode.next;
        }
        return null;
    }

No comments:

Post a Comment