合并两个已排序的链表 [英] Merging two sorted linked lists

问题描述

这是微软在笔试中提出的编程问题之一.我给出了我想出的问题和答案.事情是我的答案，虽然看起来很全面(至少对我来说)，但我觉得可以减少行数.这是用 C 语言问的，我是 Java 人，但我设法对其进行了编码(我的答案可能包含太多类似 Java 的语法)

This is one of the programming questions asked during written test from Microsoft. I am giving the question and the answer that I came up with. Thing is my answer although looks comprehensive (at least to me), I feel that the number of lines can be reduced. It was asked in C and I am a Java person but I managed to code it (my answer may contain too many Java like syntaxes)

好的，问题来了.

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

You have two lists that are already sorted, you have to merge them and return a new list without any new extra nodes. The returned list should be sorted as well.

方法签名是，

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

struct Node{
    int data;
    Node *next;
}

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

The following is the solution I came up with,

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;
}

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

I am very confident this can be enhanced. Please help me find what lines are redundantly I've added. Please feel free to criticize my syntax errors and logic.

谢谢！

推荐答案

为了处理特殊"情况而插入的 if-s 使你的代码过载读.当您决定按代码"处理特殊情况而不是找到按数据"处理它们的方法时，通常会发生这种情况.大卫·惠勒 (David Wheeler) 发表的声明说:计算机科学中的所有问题都可以通过另一个间接层次来解决".这种额外的间接级别"通常与列表配合得很好，有助于显着减少那些 if 造成的混乱.

Your code is overloaded with if-s inserted for handling "special" cases, which bloats it a lot and makes it difficult to read. This usually happens when you decide to handle special cases "by code" instead of finding a way to handle them "by data". A statement attributed to David Wheeler says "All problems in computer science can be solved by another level of indirection". That "extra level of indirection" usually works very well with lists, helping to significantly reduce clutter created by those ifs.

为了说明上述内容，这里是我的代码的样子

To illustrate the above, here's what my code would look like

#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 指针中使用额外的间接级别实际上会使代码更难阅读.我同意，对于新手来说，这种方法可能会带来一些困难，但对于有经验的程序员来说，这应该很容易理解为习语.

Some might argue that the use of an extra level of indirection in pnext pointer actually makes the code more difficult to read. I'd agree that for a newbie the approach might pose some difficulties, but for an experienced programmer this should be easily digestible as an idiom.

这篇关于合并两个已排序的链表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！