0

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?

  • O(1) space
  • No visited flag

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

Graph

Roman Oxman
  • 377
  • 6
  • 18
  • Use a set to keep track of every node you have seen, once you see a node twice you have your head – Mitch Feb 08 '21 at 22:00
  • Thanks for the answer @MitchelPaulin! Do you think there is a way to accomplish this with O(1) space? – Roman Oxman Feb 08 '21 at 22:02
  • Do your nodes have a visited flag? If you can somehow signal a node has been visited then yes you can – Mitch Feb 08 '21 at 22:05
  • Let's say it doesn't have a visited flag, I will update the question as well – Roman Oxman Feb 08 '21 at 22:07
  • Are you guaranteed the list has a cycle? – Mitch Feb 08 '21 at 22:10
  • 1
    Why wouldn't Floyd's "tortoise and hare" algorithm work? Assuming you run it for each start node (a1 and b1 in this example) it should find a loop if there is one. Can you show a case where it would fail? – samgak Feb 08 '21 at 22:22
  • You don't even need to run Floyd's for `b1`. Run it on `a1` and it will find `c2`. Done. – user3386109 Feb 08 '21 at 22:45
  • Does this answer your question? [Explain how finding cycle start node in cycle linked list work?](https://stackoverflow.com/questions/2936213/explain-how-finding-cycle-start-node-in-cycle-linked-list-work) – biqarboy Feb 08 '21 at 22:45
  • Sorry, I mistakenly raised a flag for this post. I do not know how I can remove it. Fundamentally this problem is similar to [this](https://stackoverflow.com/questions/2936213/explain-how-finding-cycle-start-node-in-cycle-linked-list-work) one, but they are not exactly the same one. – biqarboy Feb 08 '21 at 23:28
  • @user3386109 I guess after plenty of hours in LeetCode I just couldn't realize how simple this was, thanks for all your explanations and patience! – Roman Oxman Feb 09 '21 at 08:46

1 Answers1

2

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.

biqarboy
  • 852
  • 6
  • 15