合并两个已排序的链接列表

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

我非常有信心可以加强这一点.请帮我查一下我添加的冗余行.请随意批评我的语法错误和逻辑.

谢谢!

Answer 1

最明显的错误是在你的循环中,你继续覆盖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;
}

Answer 2

您的代码重载了if-s,用于处理"特殊"情况,这会使其大量增加并使其难以阅读.当您决定"通过代码"处理特殊情况而不是找到"按数据"处理它们的方法时,通常会发生这种情况.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指针中使用额外的间接级别实际上会使代码更难以阅读.我同意,对于一个新手来说,这种方法可能会带来一些困难,但对于一个有经验的程序员来说,这应该很容易理解为成语.

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

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)堆栈深度,这可能会导致堆栈溢出.此外,它不是尾递归,因此它不是编译器可优化的.