LeetCode

LeetCode-判断链表是否相交

描述：两个链表，均没有环，判断这两个链表是否相交。

关键要知道：链表中一个结点的唯一标识是它的地址。若两个结点的地址相同，表示这是同一个结点。

给出结点的定义：

1
2
3
4
5
6
7
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

方法一 遍历

对于相交的情况像字母“Y”，即只要有一个结点开始相同，那么之后的结点都相同。这种情况下，只要有相交，那么两个链表的最后一个结点一定相同。所以，分别遍历两个链表，记录尾结点，判断为节点是否是同一个结点。

时间复杂度是O(M+N)，空间复杂度是O(1)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool crossLists1(ListNode* head1, ListNode* head2){
    ListNode* dhead1 = new ListNode(-1, head1);
    ListNode* dhead2 = new ListNode(-1, head2);
    ListNode* cur1 = dhead1;
    ListNode* cur2 = dhead2;

    while (cur1->next){
        cur1 = cur1->next;
    }
    while (cur2->next){
        cur2 = cur2->next;
    }

    return cur1==cur2;
}

注意，由于链表结点的定义，指出，一个结点只有一个next指针域，所以不会出现像字母“X”的相交情况。

方法二 连接两个链表

可以将链表1的尾接到链表2的头，此时遍历链表1，如果遍历指针走到了链表的结尾，即nullptr，表示新的链表中没有环，原链表不相交；若有环，则原链表相交。

时间复杂度是O(M+N)，空间复杂度是O(1)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool crossLists2(ListNode* head1, ListNode* head2){
    if (!head1 || !head2 ) return true;
    ListNode* dhead = new ListNode(-1, head1);
    
    ListNode* needle = dhead;
    // move needle to the end of head1
    while (needle->next){
        needle = needle->next;
    }
    // link the tail of head1 to the head of head2;
    needle->next = head2;

    // check if there exists a loop
    return hasCycle(head1);
}

其中hasCycle():

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool hasCycle(ListNode* head){
    if (!head) return false;
    ListNode* fast = head;
    ListNode* slow = head;

    while(fast && slow){
        fast = fast->next;
        slow = slow->next;

        if (fast) fast = fast->next;
        // 先判断移动后的fast是否非空
        if (fast && fast==slow)
            return true;
    }
    return false;
}

方法三 使用查找表

将head1的结点放入set，然后对于head2中每个结点，在set中find()，如果能找到，则表示由公共的结点，交叉；否则不交叉。

时间复杂度：O(max(M,N)), 空间复杂度：O(M)。需要M的空间创造查找表set。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool crossLists3(ListNode* head1, ListNode* head2){
    std::set<ListNode*> st;
    ListNode* cur = head1;
    // 将head1的结点放入set
    while(cur){
        st.insert(cur);
        cur=cur->next;
    }
    cur = head2;
    // 从head2中，对每个结点在set中find，
    while(cur){
        if (st.find(cur)!=st.end())
            return true;
        cur=cur->next;
    }
    return false;
}

现在如果进一步要求出相交的结点是哪个，如何求？

方法一不适用，方法二，可以修改为带环的链表求环的入口，看笔记LeetCode-链表相关的#142。

方法三，只需要将查找表改为顺序存储，即可，如此找到的公共结点就是第一个在查找表中找到的结点。

强调：链表中一个结点的唯一标识是它的地址。当打印一个ListNode* head时，打印的是head中的内容，即一个结点对象的地址。