My Java Solution


  • 0
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null) return null;
        
        ListNode temp = headA;
        int lenA = 0;
        while(temp != null) {
            temp = temp.next;
            lenA++;
        }
        temp = headB;
        int lenB = 0;
        while(temp != null) {
            temp = temp.next;
            lenB++;
        }
        
        ListNode longer = lenA>lenB ? headA : headB;
        ListNode shorter = lenA>lenB ? headB : headA;
        int diff = Math.abs(lenA-lenB);
        while(diff != 0) {
            longer = longer.next;
            diff--;
        }
        while(longer != null && shorter != null) {
            if(longer.val == shorter.val) return longer;
            longer = longer.next;
            shorter = shorter.next;
        }
        return null;
    }
    

    main idea:

    1. find out the lengths of each of these two linked lists.
    2. align two pointers by moving extra steps at the longer list
    3. move two pointers at the same speed, and check if they are exactly the same

Log in to reply
 

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