检测两个相交的单链表中循环的开始

Question

给定两个单向链表，它们的交集后有一个循环，你如何找到循环开始的节点？[=11=]

我想到了 Floyd 的循环检测算法，但它只适用于带有循环的单链表，对吗？

在下面的示例中，要查找的节点（循环的开始）将是 C2。

是否可以满足以下要求？

O(1) space
没有访问过的标志

编辑： 不好意思大家，看到你们的评论我才知道这个问题有多么微不足道，感谢你们的耐心等待！

Answer 1

问题得到了正确的解释 here. The only difference with your requirement is, you have two singly linked lists with a loop and the solution discussed here 只考虑单向链表。但是，两个链表实际上在这里没有任何影响。

虽然您要求的是一个非常具体的案例（例如，两个相交的单链表），但我想做一个更一般的案例。那么，根据两个单向链表是否相交，是否形成循环，可以有以下几种情况：

Case-1：两个链表有单独的链，它们从不在任何共同点相遇，并且它们在各自的链中有两个循环。
Case-2：两个链表有单独的链，它们从不在任何共同点相遇，并且它们在各自的链中没有循环或其中一个有循环。
Case-3：两个链表相交，形成了一个环（你的例子）
Case-4：两个链表相交，不形成环

现在假设您有一个函数，您将指针作为函数参数传递，表示单向链接的头部。该函数将运行 Floyd 循环检测算法检查单链表是否形成任何循环。如果它找到任何循环，它总是 return 循环的起始指针。否则，return 一个空指针。您可以查看来自 here 的@CEGRD 的回答，了解有关如何编写此函数的详细信息。

之后，你可以简单地为每个单向链表分别调用这个函数，你会得到两个起始节点的循环指针（如果存在，否则你会得到空指针）。现在，如果这两个 returned 节点的指针相同（并确保它们都不是空指针），则意味着这两个链表的组合存在循环。过程应该是这样的：

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;
}

虽然我实际上并没有运行这段代码适用于任何情况，但我希望它能正常工作而不会出现任何错误。您可以尝试上面列出的不同情况并在此处发表评论。

检测两个相交的单链表中循环的开始

Detecting start of a loop in two intersecting singly Linked Lists

algorithm

linked-list

singly-linked-list