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

Question

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

Answer 1

算法描述：

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;
}