合并两个已排序的链表

这是微软笔试时提出的编程问题之一。我给出了我提出的问题和答案。事情是我的答案，虽然看起来很全面（至少对我来说），但我觉得行数可以减少。这是用 C 语言问的，我是一个 Java 人，但我设法编写了它（我的答案可能包含太多类似 Java 的语法）

好的，问题来了。

您已经有两个列表 排序后，你必须合并它们并且 返回一个新列表，没有任何新的额外内容 节点。返回的列表应该是 也排序了。

方法签名是，

Node* MergeLists(Node* list1, Node* list2);

struct Node{
    int data;
    Node *next;
}

以下是我想出的解决方案，

Node* MergeLists(Node* list1, Node* list2){
    Node* mergedList;
    if(list1 == null && list2 ==null){//if both are null, return null
        return null;
    }
    if(list1 == null){//if list1 is null, simply return list2
        return list2;
    }
    if(list2 == null){//if list2 is null, simply return list1
        return list1;
    }
    if(list1.data < list2.data){//initialize mergedList pointer to list1 if list1's data is lesser
        mergedList = list1;
    }else{//initialize mergedList pointer to list2 if list2's data is lesser or equal
        mergedList = list2;
    }
    while(list1!=null && list2!=null){
        if(list1.data < list2.data){
            mergedList->next = list1;
            list1 = list1->next;
        }else{
            mergedList->next = list2;
            list2 = list2->next;
        }
    }
    if(list1 == null){//remaining nodes of list2 appended to mergedList when list1 has reached its end.
        mergedList->next = list2;
    }else{//remaining nodes of list1 appended to mergedList when list2 has reached its end
        mergedList->next = list1;
    }
    return mergedList;
}

我非常有信心这一点可以得到加强。请帮我找出我添加的多余行。请随意批评我的语法错误和逻辑。

Thanks!

最明显的错误是在你的循环中，你不断地覆盖 mergedList->next，丢失了之前添加的节点。也就是说，无论输入如何，返回的列表都不会包含两个以上的节点......

自从我做 C 以来已经有一段时间了，但我会这样做：

Node* merge(Node* list1, Node* list2) {
    Node* merged = null;
    Node** tail = &merged;

    while (list1 && list2) {
        if (list1->data < list2->data) {
            *tail = list1;
            list1 = list1->next;
        } else {
            *tail = list2;
            list2 = list2->next;
        }
        tail = &((*tail)->next);
    }
    *tail = list1 ? list1 : list2;
    return merged;
}