两个单链表相交的第一个节点.md

求两个单链表相交的第一个节点

问题描述

求两个单链表相交的第一个节点

解决方案

**Tip:**对第一个链表遍历，计算长度len1，同时保存最后一个节点的地址。对第二个链表遍历，计算长度len2，同时检查最后一个节点是否和第一个链表的最后一个节点相同，若不相同，不相交，结束。 两个链表均从头节点开始，假设len1大于len2，那么将第一个链表先遍历len1-len2个节点，此时两个链表当前节点到第一个相交节点的距离就相等了，然后一起向后遍历，知道两个节点的地址相同

算法代码如下：

Node* List_FirstIntersectedNode(Node *head1, Node *head2) {
    if(head1 == nullptr || head2 == nullptr) return nullptr;

    int len1 = 1, len2 = 1;
    Node *tmp1 = head1;
    while (tmp1->next != nullptr) {
        tmp1 = tmp1->next;
        ++len1;
    }

    Node *tmp2 = head2;
    while (tmp2->next != nullptr) {
        tmp2 = tmp2->next;
        ++len2;
    }
    if (tmp1 != tmp2) return nullptr;

    while(len1 > len2) {
        head1 = head1->next;
        --len1;
    }

    while(len2 > len1) {
        head2 = head2->next;
        --len2;
    }

    while (head1 != head2) {
        head1 = head1->next;
        head2 = head2->next;
    }

    return head1;
}

测试用例如下：

TEST(LinkedList, List_FirstIntersectedNode) {
    Node nodeList1[10], nodeList2[10];

    EXPECT_TRUE(nullptr == List_FirstIntersectedNode(nullptr, nullptr));
    EXPECT_TRUE(nullptr == List_FirstIntersectedNode(nullptr, nodeList1));
    EXPECT_TRUE(nullptr == List_FirstIntersectedNode(nodeList1, nullptr));

    List_Init(nodeList1, 5);
    List_Init(nodeList2, 5, 10);
    EXPECT_TRUE(nullptr == List_FirstIntersectedNode(nodeList1, nodeList2));

    List_Init(nodeList1, 5);
    List_Init(nodeList2, 5, 10);
    nodeList2[4].next = &nodeList1[2];
    EXPECT_TRUE(2 == List_FirstIntersectedNode(nodeList1, nodeList2)->value);
}