假设有两个按元素值递增有序排列的带头节点的单链表A和B.试编写算法将A表和B表归并成按一个元素值递减有序(允许值下相同)排列的线性表C,要求利用原表的节点空间存放C

题目

假设有两个按元素值递增有序排列的带头节点的单链表A和B.试编写算法将A表和B表归并成按一个元素值递减有序(允许值下相同)排列的线性表C,要求利用原表的节点空间存放C

答案

/* 链表节点 */
typedef struct Node {
    int data;
    struct Node *next;
} Node;

/* 合并两个升序链表为降序链表 */
Node *merge_lists(Node *a, Node *b)
{
    Node *pa = a->next, *pb = b->next, *t;
    
    /* 新链表的头结点使用 a 的头结点 */
    a->next = NULL;
    free(b);  // b 的头结点是不需要的,可以释放掉
    
    while(pa != NULL && pb != NULL) {
        if(pa->data < pb->data) {  // 将 pa 插入新链表头部
            t = pa->next;
            pa->next = a->next;
            a->next = pa;
            pa = t;
        } else {  // 将 pb 插入新链表头部
            t = pb->next;
            pb->next = a->next;
            a->next = pb;
            pb = t;
        }
    }
    
    /* 注：以下两个循环只会执行其中一个 */
    /* 只剩链表 a 的节点 */
    while(pa != NULL) {
        t = pa->next;
        pa->next = a->next;
        a->next = pa;
        pa = t;
    }
    
    /* 只剩链表 b 的节点 */
    while(pb != NULL) {
        t = pb->next;
        pb->next = a->next;
        a->next = pb;
        pb = t;
    }
    
    return a;
}
有问题请指教 :)