Working with loops in Java using slow and fast pointers


  • 0
    D

    Here is my solution:

    public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    // Initial check
    if(headA == null || headB == null) {
    return null;
    }

        // Find tail of List B
        ListNode tailB = headB;
        while(tailB.next != null) {
            tailB = tailB.next;
        }
        
        // Make next of tailB as headB => Creating a loop
        tailB.next = headB;
        
        // Start slow and fast node references from headA
        ListNode slow = headA, fast = headA;
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            
            if(slow == fast) {
                // There is surly a intersection point in ListA and ListB
                break;
            }
        }
        
        if(fast == null || fast.next == null) {
            tailB.next = null;
            return null;
        }
        
        // Reset fast pointer to head of the list A.
        fast = headA;
        while(slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        
        // Remove the deliberately created loop
        tailB.next = null;
        
        // Return intersection point
        return fast;
    }}

Log in to reply
 

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