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

查看:107
本文介绍了合并两个排序链表的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

这是由微软笔试时提出的编程问题之一。我给的问题,我想出了答案。事情是我的回答虽然看起来COM prehensive(至少对我来说),我觉得行的数量可以减少。有人问在C和我是一个Java的人,但我设法code时(我的答案可能包含了太多的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.

谢谢!

推荐答案

您code超负荷如果 -s插入处理特殊的情况下,这涨大了很多,并且难以阅读。当你决定要处理特殊情况,由code,而不是寻找一种方法来处理它们由数据这种情况经常发生。由于大卫·惠勒的一份声明说:在计算机科学中的所有问题都可以通过间接的另一个层面来解决。这种间接额外级别通常可以非常好地列出,帮助显著减少那些如果秒。

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.

为了说明上述情况,这里就是我的code看起来像

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 指针使用间接的额外水平实际上使得code更难看了。我会同意,对于一个新手的做法可能会带来一些困难,但对于有经验的程序员,这应该是容易消化的一个成语。

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屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆