这是Microsoft进行书面测试期间提出的编程问题之一。我给出了我想出的问题和答案。尽管看起来很全面（至少对我而言），这是我的答案，但我认为可以减少行数。它是用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;
}

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

谢谢！