合并两个已排序的链表

Question

这是微软笔试中的一道编程问题。我提供了问题和我的答案，虽然我的答案看起来很全面（至少对我来说是这样），但我觉得代码行数可以减少。问题是用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;
}

我非常有信心这可以得到改进。请帮我找出哪些行是我冗余添加的。请随意批评我的语法错误和逻辑。

谢谢！

- bragboy

---

你的一些代码可以通过在开头使用三元运算符来简化。例如，重写参数测试为mergedList = (list1 == null ? list2 : null)，可以节省代码行数，尤其是在使用'not'操作时。 - Daniel Goldberg

Bragboy，你介意将你的标题改成更具描述性的形式，比如“合并两个已排序列表”吗？你现在的标题（需要您对这个编程问题的建议/提示）是我们所有人都在这里的原因。它没有识别或推广您的问题。 - edgerunner

Answer 1

最明显的 bug 在于你的循环，你不断地覆盖 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;
}

- meriton

---

哇！那是一个大洞啊！我真的没有注意到。 - bragboy

Answer 2

你的代码里充斥着为了处理“特殊”情况而插入的if语句，这使得代码变得臃肿且难以阅读。通常情况下，当你决定通过编写代码来处理特殊情况而不是寻找一种通过数据来处理它们的方式时，就会出现这种情况。David Wheeler曾说过：“计算机科学中的所有问题都可以通过另一层间接性来解决。”那个“额外的间接层”通常与列表很好地配合使用，有助于显著减少由这些if语句创建的混乱。

为了说明上述观点，以下是我的代码示例：

#define SWAP_PTRS(a, b) do { void *t = (a); (a) = (b); (b) = t; } while (0)

Node* MergeLists(Node* list1, Node* list2) 
{
  Node *list = NULL, **pnext = &list;

  if (list2 == NULL)
    return list1;

  while (list1 != NULL)
  {
    if (list1->data > list2->data)
      SWAP_PTRS(list1, list2);

    *pnext = list1;
    pnext = &list1->next;
    list1 = *pnext;
  }

  *pnext = list2;
  return list;
}

有人可能会认为在 pnext 指针中使用额外的间接层级实际上使代码更难读。我同意对于新手来说，这种方法可能会带来一些困难，但对于经验丰富的程序员来说，这应该很容易被理解为一种惯用法。

- AnT stands with Russia

---

谢谢。将来在解决这类问题时会考虑采用这种方法。真的很有帮助！ - bragboy

如果list2传入了null，那么这个尝试去解引用null会出错吗？ - meriton

@meriton：是的，这样做会更好。我添加了额外的检查 :) 谢谢。 - AnT stands with Russia

+1 是为了解释间接寻址和简化 while 循环条件，只检查修改后的指针。 - meriton

为什么不将这两行代码改为 list1 = list1->next;？ - Josh Morrison

Answer 3

我的看法，附带一个测试案例

到目前为止，所有的答案都很有趣并且做得很好。这个答案可能更像面试官想要看到的，包括DRY/DIE和TDD。:-)

#include <stdio.h>

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

Node l1[] = {
  { 1, &l1[1] },
  { 3, &l1[2] },
  { 5, &l1[3] },
  { 7, &l1[4] },
  { 9, &l1[5] },
  {11, 0 },
};

Node l2[] = {
  { 2, &l2[1] },
  { 4, &l2[2] },
  { 6, 0 },
};

Node* MergeLists(Node* list1, Node* list2) {
  Node *t, **xt;
  for(xt = &t; list1 || list2;) {
    Node **z = list1 == NULL ? &list2 :
               list2 == NULL ? &list1 :
               list1->data < list2->data ? &list1 : &list2;
    *xt = *z;
     xt = &(*z)->next;
    *z  = *xt;
  }
  *xt = NULL;
  return t;
}

int main(void) {
  for(Node *t = MergeLists(l1, l2); t; t = t->next) 
    printf("%d\n", t->data);
  return 0;
}

- DigitalRoss

---

那是一种巧妙的构建链表的方法。喜欢它。 - polygenelubricants

Answer 4

没有比这更优雅的了：

Node* merge2(Node* n1, Node* n2) {
    n1->next = merge(n1->next, n2);
    return n1;
}

Node* merge(Node* n1, Node* n2) {
    return (n1 == null) ? n2 :
           (n2 == null) ? n1 :
           (n1->data < n2->data) ?
               merge2(n1, n2) :
               merge2(n2, n1);
}

假设您了解递归，那么这就是最清晰的表述。

---

我应该指出，这只适用于面试答案（在面试中展示思维清晰度比仅仅展示编写程序技能更有影响力）。实际上，您不会想以这种方式合并，因为它使用 O(n) 堆栈深度，可能会导致堆栈溢出。此外，它不是尾递归，因此无法进行编译器优化。

- polygenelubricants

---

嗯，需要一些时间来适应，但除非滥用它，否则对我来说，嵌套三元运算符实际上可以使代码非常清晰。它需要良好的逻辑和良好的格式化，一些括号和一些缩进，但仅此而已。 - polygenelubricants

我发现在没有IDE的帮助下编写递归方法非常困难。我总是想在最终确定之前进行一两次测试。这就是为什么我尽可能避免使用它的原因。 - bragboy

在某种意义上，它使用了递归，因此显得“优雅”。但从功能角度来看，在直接的循环情况下使用递归并不完全是函数式优美的例子。任何循环都可以用递归代替。但是否应该这样做呢？ - AnT stands with Russia

如果我是你，我会抵制创建额外函数的需求 :) 你可以使用,运算符轻松地只用一个函数完成它。最后一支分支看起来只需要这样：n1->data < n2->data ? n1->next = merge(n1->next, n2), n1 : n2->next = merge(n2->next, n1), n2。但这开始有点像混淆C代码比赛 :) - AnT stands with Russia

是的，你的解决方案和我的区别在于，你的（在修复所有错误后）表明作者知道如何编写正确的代码。而我的则表明作者知道如何清晰地思考。 - polygenelubricants

Answer 5

分而治之

(即归并排序)

- Luca

---

这正是正确的答案，为什么会有踩？@Luca：我给你点赞。 - tzaman

@tzaman：这到底跟这个问题有什么关联啊？ - bragboy

@Bragaadeesh：你必须排序吗？我想知道为什么不使用众所周知的算法。毫无疑问，使用分治模式可以获得最佳性能，而不是简单地迭代两个列表。这只是关于算法模式的批评，实际上它对我来说似乎很相关。 - Luca

我也给你点了赞。这正是归并排序中的合并部分。 - Larry

啊！拜托各位，完整地阅读问题。这不是关于排序算法的问题。数据已经排好序了。这个问题更多地涉及编程风格。 - bragboy

这是关于合并两个已排序列表的问题。归并排序的第二部分就是合并两个已排序列表，非常简单明了。 - Ross

Answer 6

使用递归。代码如下：

ListNode* mergeTwoSortedLists(ListNode* pHead1, ListNode* pHead2)
{
    if(pHead1 == NULL)
        return pHead2;
    else if(pHead2 == NULL)
        return pHead1;

    ListNode* pMergedHead = NULL;

    if(pHead1->m_nValue < pHead2->m_nValue)
    {
        pMergedHead = pHead1;
        pMergedHead->m_pNext = mergeTwoSortedLists(pHead1->m_pNext, pHead2);
    }
    else
    {
        pMergedHead = pHead2;
        pMergedHead->m_pNext = mergeTwoSortedLists(pHead1, pHead2->m_pNext);
    }

    return pMergedHead;
}

- herohuyongtao

Answer 7

因此，将polygen与AndreyT合并，我们得到：

Node* merge(Node* n1, Node* n2) {
    return (n1 == null) ? n2 :
           (n2 == null) ? n1 :
             (n1->data < n2->data) ? 
               (n1->next = merge(n1->next, n2), n1) : 
               (n2->next = merge(n2->next, n1), n2)}

我不会为这个贡献自己的功劳，但这是最简洁的，并展示了两个参数之间的对称性，没有引入任何模糊的辅助函数。我不确定一个优化编译器是否会看到这里的尾递归，但是我可以看到。缩进是最后一步。

- piccolbo

Answer 8

这道题我的 Golang 解法：

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    head1 := list1
    head2 := list2
    ans := &ListNode{}
    tail := ans
    for head1 != nil && head2 != nil {
        if head1.Val > head2.Val {
            tail.Next = head2
            head2 = head2.Next
            tail = tail.Next
        } else {
            tail.Next = head1
            head1 = head1.Next
            tail = tail.Next
        }
    }

    if head1 != nil {
        tail.Next = head1
    }
    if head2 != nil {
        tail.Next = head2
    }
    return ans.Next
}

给定列表： list1 = 1->2->3 list2 = 1->2->4->5

输出结果：1->1->2->2->3->4->5

定义一个空列表，如果满足以下任一条件，则将元素推到最后。

最后返回ans.next，它将是新创建的列表的当前头部。

- Kamal Kant

Answer 9

#include<stdio.h>

typedef struct NODE
{
    int data;
    struct NODE * next;
}NODE;

NODE * func(NODE*,NODE*);
int main()
{
    int i;
    int size;
    int value;
    NODE * head1,*head2,*newNode,*ptr,*final;
    printf("\nPlease enter the number of elements\n");
    scanf("%d",&size);

    for(i=0;i<size;i++)
    {
            printf("List 1\n");
            printf("Please enter the value number %d \n",i+1);
            scanf("%d",&value);
            newNode=(NODE*)malloc(sizeof(NODE));
            newNode->data=value;
            newNode->next=NULL;
            if(i!=0)
            {
                ptr->next=newNode;  
                ptr=ptr->next;
            }

            if(i==0)
            {
                head1=newNode;
                ptr=newNode;

            }
    }
    for(i=0;i<size;i++)
    {
            printf("\n\nList 2\n");
            printf("Please enter the value number %d \n",i+1);
            scanf("%d",&value);
            newNode=(NODE*)malloc(sizeof(NODE));
            newNode->data=value;
            newNode->next=NULL;
            if(i!=0)
            {
                ptr->next=newNode;  
                ptr=ptr->next;
            }

            if(i==0)
            {
                head2=newNode;
                ptr=newNode;

            }
    }

    final=func(head1,head2);
    printf("\n\n");
    while (final!=NULL)
    {
        printf("%d -->",final->data);
        final=final->next;
    }
    printf("NULL
    ");
    return 0;
}

NODE* func(NODE* list1, NODE* list2)
{

    NODE* mergedList,*mergeHead=NULL;
    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;
    }
    mergedList = (NODE*)malloc(sizeof(NODE));
    if(list1->data < list2->data){//initialize mergedList pointer to list1 if list1's data is lesser

        mergedList->data=list1->data;
        mergedList->next=NULL;
        list1 = list1->next;

    }else{//initialize mergedList pointer to list2 if list2's data is lesser or equal
        mergedList->data=list2->data;
        mergedList->next=NULL;
        list2 = list2->next;

    }
    mergeHead=mergedList;

    while(list1!=NULL && list2!=NULL){
        if(list1->data < list2->data){
            mergedList->next = (NODE*)malloc(sizeof(NODE));
            mergedList=mergedList->next;
            mergedList->data=list1->data;
            mergedList->next=NULL;
            list1 = list1->next;
        }else{
            mergedList->next = (NODE*)malloc(sizeof(NODE));
            mergedList=mergedList->next;
            mergedList->data=list2->data;
            mergedList->next=NULL;
            list2 = list2->next;
        }
    }
    if(list1 == NULL){//remaining nodes of list2 appended to mergedList when list1 has reached its end.
       while(list2!=NULL)
       {
            mergedList->next = (NODE*)malloc(sizeof(NODE));
            mergedList=mergedList->next;
            mergedList->data=list2->data;
            mergedList->next=NULL;
            list2 = list2->next;
       }

    }else{//remaining nodes of list1 appended to mergedList when list2 has reached its end
            mergedList->next = (NODE*)malloc(sizeof(NODE));
            mergedList=mergedList->next;
            mergedList->data=list1->data;
            mergedList->next=NULL;
            list1 = list1->next;
    }
    return mergeHead;
}

- Abhishek Jadhav

Answer 10

public void Merge(LinkList list1, LinkList list2) {
        if (list1.head == null && list2.head == null) {
            System.out.println("Empty list"); //Check if lists are empty
        }
        if (list1.head == null) { //If list1 is empty print list2
            list2.printList();
        }
        if (list2.head == null) { //If list2 is empty print list1
            list1.printList(); 
        }
        LinkList list3 = new LinkList(); //create a new LinkList object for merging
        Node a = list1.head; //Beginning of list1
        Node b = list2.head; //Beginning of list2
        while (a != null && b != null) { //Until list ends
            if (a.value <= b.value) { //Compare values of list1 against list2
                list3.insert(a.value); //Insert values to new list
                a = a.next;
            } else if (a.value >= b.value) {
                list3.insert(b.value);
                b = b.next;
            }  else if (a.value == b.value){ //Insert only unique values and discard repeated values
            list3.insert(a.value);
            a = a.next;
            b = b.next;
        }
        }
        if (a == null) {
            while (b != null) {
                list3.insert(b.value); //If list1 becomes empty, attach rest of the list2 to list3
                b = b.next;
            }
        }
        if (b == null) {
            while (a != null) {
                list3.insert(a.value);
                a = a.next;
            }
        }
        list3.printList(); //print merged list
    }
}

大家好！我正在为这个月的面试做准备，当我在解决这个问题时，我想到了这个解决方案。我将我的解决方案与你们发布的众多解决方案进行了比较，并发现我的程序非常冗长。虽然我觉得这个实现更容易理解和实现，但是是否有更好的Java解决方案来改进现有的代码。我正在寻找更好的时间复杂度解决方案。任何帮助/指导/提示都将不胜感激。

PS：对于使用指针的C语言程序，我无法提供Java解决方案。

- Naveen