关于#数据结构#的问题，如何解决？

求解一道数据结构题目，要求使用c语言。已知两个带表头节点的单链表A和B，其元素值递增排序，设计一个算法，将A和B合并成一个递减有序（相同值只保留一个）的链表C，并要求利用原表结点。要求给出问题求解的算法描述，并分析其时间复杂度。最好给一下代码。

算法描述：

1. 定义链表C为空链表。
2. 初始化指针pa指向链表A的第一个结点，指针pb指向链表B的第一个结点。
3. 遍历链表A和链表B，比较当前结点的值，将较小值的结点插入链表C的头部。
4. 最后将链表C逆序，保留相同值的结点。

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

代码实现：

#include <stdlib.h>

struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode* merge_lists(struct ListNode* A, struct ListNode* B){
    // 定义链表C为空链表
    struct ListNode* C = (struct ListNode*)malloc(sizeof(struct ListNode));
    C->next = NULL;
    // 初始化指针pa和pb
    struct ListNode *pa = A->next, *pb = B->next;
    // 遍历链表A和链表B
    while (pa && pb) {
        if (pa->val <= pb->val) {
            // 将较小值的结点插入链表C的头部
            struct ListNode* tmp = pa->next;
            pa->next = C->next;
            C->next = pa;
            pa = tmp;
        } else {
            struct ListNode* tmp = pb->next;
            pb->next = C->next;
            C->next = pb;
            pb = tmp;
        }
    }
    // 处理剩余结点
    if (pa) {
        struct ListNode* tmp = pa->next;
        pa->next = C->next;
        C->next = pa;
        pa = tmp;
    }
    if (pb) {
        struct ListNode* tmp = pb->next;
        pb->next = C->next;
        C->next = pb;
        pb = tmp;
    }
    // 逆序链表C
    struct ListNode *prev = NULL, *curr = C->next;
    while (curr) {
        struct ListNode* next_node = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next_node;
    }
    // 删除相同值的结点
    curr = prev;
    while (curr && curr->next) {
        if (curr->val == curr->next->val) {
            curr->next = curr->next->next;
        } else {
            curr = curr->next;
        }
    }
    return prev;
}

链表合并

有帮助的话 采纳一下

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

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

typedef struct LinkList {
    Pnode head; 
} LinkList, *plinkList;

// 创建一个单链表
plinkList CreateList() {
    plinkList L = (plinkList) malloc(sizeof(LinkList));
    L->head = NULL;
    return L;
}

// 向链表尾部插入一个节点
void InsertNode(plinkList L, int data) {
    Pnode s = (Pnode) malloc(sizeof(Node));
    s->data = data;
    s->next = NULL;
    
    if (L->head == NULL) {
        L->head = s;
    } else {
        Pnode p = L->head;
        while (p->next) p = p->next;
        p->next = s;
    }
} 

// 输出单链表的所有节点
void PrintList(plinkList L) {
    Pnode p = L->head;
    while (p) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

// 归并两个递增链表A和B,产生一个递减链表C
plinkList MergeList(plinkList A, plinkList B) {
    Pnode pa = A->head, pb = B->head;
    Pnode pc = NULL;   // C的头节点
    
    Pnode p = NULL;    // pc的尾节点
    while (pa && pb) {
        if (pa->data > pb->data) { 
            if (pc == NULL) {   // C链表为空,将较大值节点设为头节点
                pc = pa;
                p = pa;       
                pa = pa->next;
            } else {            // 插入到C链表尾部
                p->next = pa;   
                p = pa;       
                pa = pa->next;
            }
        } else {
            if (pc == NULL) {   // C链表为空,将较大值节点设为头节点
                pc = pb;
                p = pb;   
                pb = pb->next; 
            } else {
                p->next = pb;    
                p = pb;       
                pb = pb->next;
            } 
        }
    }
    
    // 将未到达尾节点的链表直接接到pc后面
    if (pa) p->next = pa; 
    if (pb) p->next = pb;
    
    return pc;
}

int main() {
    plinkList A = CreateList();
    InsertNode(A, 1);
    InsertNode(A, 3);
    InsertNode(A, 5);
    PrintList(A);
    
    plinkList B = CreateList();
    InsertNode(B, 2); 
    InsertNode(B, 4);
    InsertNode(B, 6);
    InsertNode(B, 8);
    PrintList(B);
    
    plinkList C = MergeList(A, B);
    PrintList(C);
    
    return 0;
}