Skip to content

Latest commit

 

History

History
44 lines (34 loc) · 1.56 KB

两个单链表是否相交.md

File metadata and controls

44 lines (34 loc) · 1.56 KB

判断两个单链表是否相交

问题描述

判断两个单链表是否相交

解决方案

**Tip:**如果两个链表相交于某一节点,那么在这个相交节点之后的所有节点都是两个链表所共有的。也就是说,如果两个链表相交,那么最后一个节点肯定是共有的。先遍历第一个链表,记住最后一个节点,然后遍历第二个链表,到最后一个节点时和第一个链表的最后一个节点做比较,如果相同,则相交,否则不相交。时间复杂度为O(len1+len2),因为只需要一个额外指针保存最后一个节点地址,空间复杂度为O(1)。

算法代码如下:

bool List_IsIntersected(Node *head1, Node *head2) {
    if(head1 == nullptr || head2 == nullptr) return false;

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

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

    return (head1 == head2);
}

测试用例如下:

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

    EXPECT_TRUE(false == List_IsIntersected(nullptr, nullptr));
    EXPECT_TRUE(false == List_IsIntersected(nullptr, nodeList1));
    EXPECT_TRUE(false == List_IsIntersected(nodeList1, nullptr));

    List_Init(nodeList1, 5);
    List_Init(nodeList2, 5, 10);
    nodeList2[4].next = &nodeList1[2];
    EXPECT_TRUE(true == List_IsIntersected(nodeList1, nodeList2));

    List_Init(nodeList1, 5);
    List_Init(nodeList2, 5, 10);
    EXPECT_TRUE(false == List_IsIntersected(nodeList1, nodeList2));
}