两个链表的交集问题

Question

我使用的方法是： -> 为每个列表选取两个虚拟节点。将每个都指向列表的头部。 -> 迭代它们。如果任何一个变为空，将它们指向相反列表的头部并继续迭代，直到它们发生碰撞。

为什么这段代码不起作用？

ListNode *getIntersectionNode(ListNode *l1, ListNode *l2) {
        if(l1 == NULL && l2 == NULL) return NULL;
        ListNode* d1 = l1;
        ListNode* d2 = l2;
        while(d1 != NULL && d2 != NULL) {
            if(d1 == d2) {
                return d1;
            }
            if(d1 == NULL && d2 != NULL) d1 = l2;
            if(d2 == NULL && d1 != NULL) d2 = l1;
            d1 = d1 -> next;
            d2 = d2 -> next;
        }
        return NULL;
    }

Answer 1

这些行有错误。

if(d1 == NULL && d2 != NULL) d1 = l2;
if(d2 == NULL && d1 != NULL) d2 = l1;

这些条件位于 while 循环内，并且它们的顺序不正确。您应该首先将 d1 和 d2 前进到它们的下一个节点，然后检查它们是否变为空。以下是更正后的版本。

ListNode *getIntersectionNode(ListNode *l1, ListNode *l2) {

        if (l1 == NULL || l2 == NULL) return NULL;
        
        ListNode* d1 = l1;
        ListNode* d2 = l2;
        
        while (d1 != d2) {
            d1 = (d1 == NULL) ? l2 : d1->next;
            d2 = (d2 == NULL) ? l1 : d2->next;
        }
        
        return d1;
    }

在 return 语句中，可以返回 d1 或 d2，因为它们将在交点处相遇，如果没有交集，则返回 NULL。现在，在将 d1 和 d2 推进到下一个节点后，更新 d1 和 d2 的条件已正确放置。