Sharing java solution with fast/slow pointer


  • 1
    L
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode endA = null;
        ListNode currentA, currentB;
        if (headA == null || headB == null) return null;
        
        endA = headA;
        while(endA.next != null) endA = endA.next; // Find end of A
        endA.next = headA;                         // Build loop
        
        currentB = headB;
        while(currentB != null) { // Go from head of B
            if (currentB == headA) break; // If hit head of A, found loop from B
            else currentB = currentB.next;
        }
        
        if (currentB == null) { // If get out of above loop by this, no intersection found.
            endA.next = null;
            return null;        // Restore and return.
        }
        
        currentA = headB;
        currentB = headB;
        do {                    // Use fast/slow pointers to find the node in loop that has the same
            currentA = currentA.next;   // distance to the intersection node comparing to headB
            currentB = currentB.next.next;
        } while(currentA != currentB);
        
        currentB = headB;
        while(currentA != currentB) {  // Start from headB again to find intesection.
            currentA = currentA.next;
            currentB = currentB.next;
        }
        
        endA.next = null;
        return currentA;
    }

Log in to reply
 

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