合并两个排序的链表

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

要求：

• 结果链表仍然使用两个链表的存储空间，不另外占用其他的存储空间；
• 表中不允许有重复的数据；

示例:

输入：1->2->4, 1->3->4
输出：1->2->3->4

解题思路：

根据题目描述，链表La，Lb是递增的，因此很容易想到使用双指针便利两个链表，根据判断大小关系确定节点添加顺序，两节点指针交替进行，直至遍历完毕；

复杂度分析：

• 时间复杂度O(M + N)：M，N分别为链表的长度。
• 空间复杂度 O(1)

代码：

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

void mergeTwoLists(LinkList *La, LinkList *Lb, LinkList *Lc) {
    LinkList pa, pb, pc, temp;
    pa = (*La)->next;
    pb = (*Lb)->next;
    *Lc = pc = *La;
    while (pa && pb) {
        if (pa->data < pb->data) {
            pc->next = pa;
            pc = pa;
            pa = pa->next;
        } else if (pa->data > pb->data) {
            pc->next = pb;
            pc = pb;
            pb = pb->next;
        } else {
            pc->next = pa;
            pc = pa;
            pa = pa->next;

            temp = pb->next;
            free(pb);
            pb = temp;
        }
    }
    pc->next = pa == NULL ? pb : pa;
    free(*Lb);
}