单链表找公共结点时间复杂度

单链表找公共结点的时间复杂度是O(m + n)，其中m和n分别是两个链表的长度。

要找到两个单链表的公共结点，可以先分别遍历两个链表，得到它们的长度。然后让较长的链表先移动差值个结点，使得两个链表剩余的长度相等。接下来同时遍历两个链表，比较每个结点是否相同，直到找到第一个相同的结点或者遍历到链表的末尾。

由于需要遍历两个链表，所以时间复杂度为O(m + n)。

相关问题

设A和B是两个单链表（带头结点），其中元素递增有序。设计一个算法，从A和B中的公共元素产生单链表C，要求不破坏A、B的结点

结构。

算法思路：

1. 分别从A和B的头结点开始，比较当前结点的值。

2. 如果A当前结点的值小于B当前结点的值，则A指针后移，否则B指针后移。

3. 如果A当前结点的值等于B当前结点的值，则将该结点插入到C链表的末尾，并将A和B指针同时后移。

4. 直到A或B的指针指向NULL为止。

5. 返回C链表的头结点。

时间复杂度为O(min(m,n))，其中m和n分别为A和B链表的长度。

算法实现：

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x): val(x), next(NULL) {}
};

ListNode* getIntersection(ListNode* A, ListNode* B) {
    ListNode* C = new ListNode(0);
    ListNode* tail = C;
    while (A != NULL && B != NULL) {
        if (A->val < B->val) {
            A = A->next;
        } else if (A->val > B->val) {
            B = B->next;
        } else {
            ListNode* node = new ListNode(A->val);
            tail->next = node;
            tail = tail->next;
            A = A->next;
            B = B->next;
        }
    }
    return C->next;
}

int main() {
    ListNode* A = new ListNode(1);
    A->next = new ListNode(3);
    A->next->next = new ListNode(5);
    A->next->next->next = new ListNode(7);
    A->next->next->next->next = new ListNode(9);

    ListNode* B = new ListNode(2);
    B->next = new ListNode(3);
    B->next->next = new ListNode(4);
    B->next->next->next = new ListNode(7);
    B->next->next->next->next = new ListNode(8);

    ListNode* C = getIntersection(A, B);

    while (C != NULL) {
        cout << C->val << " ";
        C = C->next;
    }

    return 0;
}

输出结果为：3 7

设A和B是两个单链表（带头结点），其中元素递增有序。设计一个算法，从A和B中的公共元素产生单链表C，要求不破坏A、B的结点。

首先，我们可以分别遍历A和B，对于相同的元素，将其添加到单链表C中。我们可以使用两个指针p和q分别指向A和B的头结点，然后进行如下操作：

1. 如果p->next的值小于q->next的值，则p向后移动一位；
2. 如果p->next的值大于q->next的值，则q向后移动一位；
3. 如果p->next的值等于q->next的值，则将其添加到单链表C中，并且p和q都向后移动一位。

最终，单链表C中存储的就是A和B中的公共元素。这个算法的时间复杂度为O(m+n)，其中m和n分别是A和B的长度。