设A和B是两个结点个数分别为m和n的单链表（带头结点），其中元素递增有序。设计一个尽可能高效的算法求A和B的交集，要求不破坏A、B的结点，将交集存放在单链表C中。给出你所设计的算法的时间复杂度和空间复杂度

可以通过双指针遍历A和B单链表，将相同元素添加到新的单链表C中。具体实现可以如下：

1. 首先创建一个新的单链表C，用于存放交集。
2. 定义两个指针pA和pB，分别指向A和B的头结点的下一个结点。
3. 遍历A和B单链表，如果pA所指结点的值小于pB所指结点的值，则pA指向下一个结点；如果pA所指结点的值大于pB所指结点的值，则pB指向下一个结点；如果pA所指结点的值等于pB所指结点的值，则将该结点添加到单链表C中，并将pA和pB同时指向下一个结点。
4. 当pA或pB为空时，停止遍历，返回单链表C。

时间复杂度：O(m+n)，其中m和n分别为A和B的结点个数。

空间复杂度：O(min(m,n))，即新建单链表C所需的空间。

相关问题

设a和b是两个结点个数分别为m和n的单链表（带头结点），其中元素递增有序。设计一个尽可能高效的算法求a和b的交集，要求不破坏a、b的结点，将交集存放在单链表c中。给出你所设计的算法的时间复杂度和空间复

杂度。

算法思路：

1. 定义三个指针p、q、r，分别指向链表a、b、c的头结点。

2. 遍历链表a和b，比较a和b当前结点的值大小，如果相等，则将该结点插入到链表c中，并将p、q、r分别指向下一个结点；如果a当前结点的值小于b当前结点的值，则将p指向下一个结点；如果a当前结点的值大于b当前结点的值，则将q指向下一个结点。

3. 当p或q指向空结点时，算法结束。

算法时间复杂度为O(m+n)，空间复杂度为O(1)。

算法实现：

typedef struct Node {
    int data;
    struct Node *next;
} Node, *LinkedList;

LinkedList intersection(LinkedList a, LinkedList b) {
    LinkedList c = (LinkedList)malloc(sizeof(Node));
    c->next = NULL;
    Node *p = a->next, *q = b->next, *r = c;
    while (p && q) {
        if (p->data == q->data) {
            Node *node = (Node*)malloc(sizeof(Node));
            node->data = p->data;
            node->next = NULL;
            r->next = node;
            r = r->next;
            p = p->next;
            q = q->next;
        } else if (p->data < q->data) {
            p = p->next;
        } else {
            q = q->next;
        }
    }
    return c;
}

设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