设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的长度。

相关问题

设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合并到一个单链表C中，单链表C仍然递增有序。C语言代码

以下是将两个带头结点的有序单链表A和B合并到一个单链表C中，并保持C有序的C语言代码：

#include<stdio.h>
#include<stdlib.h>

struct Node {
    int data;
    struct Node* next;
};

// 创建一个带头结点的单链表
struct Node* createLinkedList() {
    struct Node* head = (struct Node*)malloc(sizeof(struct Node));
    head->next = NULL;
    return head;
}

// 将值为value的结点插入到带头结点的单链表中
void insertNode(struct Node* head, int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = NULL;

    struct Node* cur = head;
    while (cur->next != NULL && cur->next->data < value) {
        cur = cur->next;
    }
    newNode->next = cur->next;
    cur->next = newNode;
}

// 合并两个带头结点的有序单链表A和B到一个带头结点的有序单链表C中
struct Node* mergeLinkedList(struct Node* A, struct Node* B) {
    struct Node* C = createLinkedList();
    struct Node* curA = A->next;
    struct Node* curB = B->next;

    while (curA != NULL && curB != NULL) {
        if (curA->data < curB->data) {
            insertNode(C, curA->data);
            curA = curA->next;
        }
        else {
            insertNode(C, curB->data);
            curB = curB->next;
        }
    }

    while (curA != NULL) {
        insertNode(C, curA->data);
        curA = curA->next;
    }

    while (curB != NULL) {
        insertNode(C, curB->data);
        curB = curB->next;
    }

    return C;
}

// 输出带头结点的单链表中的所有结点值
void printLinkedList(struct Node* head) {
    struct Node* cur = head->next;
    while (cur != NULL) {
        printf("%d ", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

// 测试
int main() {
    struct Node* A = createLinkedList();
    insertNode(A, 1);
    insertNode(A, 3);
    insertNode(A, 5);
    printf("A: ");
    printLinkedList(A);

    struct Node* B = createLinkedList();
    insertNode(B, 2);
    insertNode(B, 4);
    insertNode(B, 6);
    printf("B: ");
    printLinkedList(B);

    struct Node* C = mergeLinkedList(A, B);
    printf("C: ");
    printLinkedList(C);

    return 0;
}

在这个程序中，我们首先创建了一个带头结点的单链表，然后通过 `insertNode` 函数将数据插入到单链表中。在 `mergeLinkedList` 函数中，我们使用了两个指针 `curA` 和 `curB` 分别指向链表 A 和 B 的第一个数据结点，然后依次比较这两个指针指向的结点的值，将较小的结点插入到链表 C