Java, 2ms, O(n) time, O(1) space solution


  • 4
    J

    Find the lengths of both lists, and if they intersect, then the extra nodes in the front of the longer list should be disregarded, and from that point on, the two list should be synchronized, and you should expect to see a intersection when you are traversing the two lists at the same time.

    public class Solution {
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            if (headA == null || headB == null) return null;
            
        int numA = 0, numB = 0;
        ListNode nA = headA, nB = headB, longList = null, shortList = null, commonNode = null;
        while(nA != null){
            numA++;
            nA = nA.next;
        }
        while(nB != null){
            numB++;
            nB = nB.next;
        }
        
        longList = (numA >= numB ? headA : headB);
        shortList = (numA >= numB ? headB : headA);
        for (int i = 0; i < Math.abs(numA - numB); i++){
            longList = longList.next;
        }
        while(longList != null){
            if (commonNode == null && longList == shortList){
                commonNode = longList;
            }
            if (commonNode != null && longList != shortList)
                return null;
            longList = longList.next;
            shortList = shortList.next;
        }
        
        return commonNode;
    }
    

    }


  • 0
    I

    Once you find a common node, you don't need to check the consequent ones for equality, since you're not comparing their value, but their identity instead.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.