CODEWITHSUNDEEP
algorithmlinked-listsingly-linked-list
Roman Oxman
Roman Oxman

Reputation: 397

Detecting start of a loop in two intersecting singly Linked Lists

Given two singly linked lists with a loop after their intersection, how can you find the node where the cycle begins?

I thought about Floyd's cycle detection algorithm but that only works for a single linked list with a loop, right?

In the example below, the node to find (start of the cycle) would be C2.

Is it possible to do it with the following requirements?

Edit: Sorry guys, I didn't realize how trivial this question was until reading your comments, thanks for the patience!

Graph

Upvotes: 0

Views: 553

Answers (1)

biqarboy
biqarboy

Reputation: 852

The problem is answered with proper explanation here. The only difference with your requirement is, you have two singly linked lists with a loop and the solution discussed here only considered a singly linked list. But, two linked list actually do not have any impact here.

Although you asked for a very specific case (e.g., two intersecting singly Linked Lists), but I would like to make a more general one. So, with two singly linked list based on whether they intersect or not, and whether they form cycle or not, you can have the following cases:

  1. Case-1: Two linked lists have separate chain, they never meet at any common place, and they have two cycles in their respective chains.
  2. Case-2: Two linked lists have separate chain, they never meet at any common place, and they have either no-cycle in their respective chains or one of them have a cycle.
  3. Case-3: Two linked lists intersect, and they have formed a cycle (your example case).
  4. Case-4: Two linked lists intersect, and they do not form any cycle.

Now consider you have a function where you pass a pointer as a function parameter representing the head of a singly linked. This function will run Floyd's cycle detection algorithm to check whether the singly linked list form any cycle. If it found any cycle, it always return the starting pointer of the cycle. Otherwise, return a null pointer. You can check @CEGRD's answer from here to know the details about how you can write this function.

After that, you can simply call this function for every singly linked list separately and you will get two starting nodes' pointer of cycle (if exist, otherwise you will get null pointer). Now, if these two returned nodes' pointer are same (and make sure both of them are not null-pointer), means a cycle exist for the combination of this two linked lists. The process should be like this:

ListNode *detectCycle(ListNode *head) {
    ListNode *walker = head;
    ListNode *runner = head;

    while(runner != nullptr && runner->next != nullptr) {
        walker = walker->next;
        runner = runner->next->next;

        if(walker == runner) {
            ListNode *seeker = head;

            while(seeker != walker) {
                seeker = seeker->next;
                walker = walker->next;
            }
            return walker;
        }
    }

    return nullptr;
}

// headA and headB are the head pointer of cycle A and B respectively.
ListNode *detectCycleInTwoLinkedList(ListNode *headA, ListNode *headB) {
    ListNode * ca = detectCycle(headA)
    ListNode * cb = detectCycle(headB)

    if(ca == nullptr || cb == nullptr) return nullptr;
    return (ca == cb) ? ca : nullptr;
}

Although I didn't actually run this code for any case, but I hope it will work without any error. You can try for the different cases listed above and comment here.

Upvotes: 2

Related Questions