C语言 合并两个已排序的链表

Merging two sorted linked lists

提问by bragboy

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)

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

Ok, here is the question.

好的，问题来了。

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.

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

The method signature is,

方法签名是，

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.

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

Thanks!

谢谢！

采纳答案by AnT

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.

您的代码if因处理“特殊”情况而插入的 -s过载，这使代码膨胀很多并使其难以阅读。当您决定“按代码”处理特殊情况而不是找到“按数据”处理它们的方法时，通常会发生这种情况。大卫·惠勒 (David Wheeler) 发表的声明说：“计算机科学中的所有问题都可以通过另一个间接层次来解决”。“额外的间接级别”通常与列表配合得很好，有助于显着减少由这些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;
}

Some might argue that the use of an extra level of indirection in pnextpointer 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.

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

回答by meriton

The most glaring bug is in your loop, you keep overwriting mergedList->next, losing the previously added node. That is, your returned list will never contain more than two nodes, regardless of input ...

最明显的错误是在你的循环中，你不断覆盖 mergeList->next，丢失了之前添加的节点。也就是说，无论输入如何，您返回的列表永远不会包含两个以上的节点...

It's been a while since I did C, but I would do it as follows:

自从我做 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;
}

回答by DigitalRoss

My take, with a test case

我的看法，有一个测试用例

So far all of the answers have been interesting and well done. It's possible that this one is more like what an interviewer would like to see, featuring DRY/DIE, and TDD. :-)

到目前为止，所有的答案都很有趣，而且做得很好。这可能更像是面试官希望看到的，具有 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;
}

回答by polygenelubricants

It doesn't get any more elegant than this:

没有比这更优雅的了：

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

Assuming that you understand recursion, this is as clear as it gets.

假设您了解递归，这就很清楚了。

---

---

I should point out that this is good for an interview answer only (where presumably demonstrating clarity of thought has more impact than simply showing that you know how to write programs). In practice, you wouldn't want to merge this way, since it uses O(n)stack depth, which likely would cause a stack overflow. Also, it's not a tail-recursion, so it's not compiler-optimizable.

我应该指出，这仅适用于面试答案（大概证明思路清晰比简单地表明您知道如何编写程序具有更大的影响）。实际上，您不会希望以这种方式合并，因为它使用O(n)堆栈深度，这可能会导致堆栈溢出。此外，它不是尾递归，因此它不是编译器可优化的。

回答by Luca

Divide et Impera

分而治之

(i.e. MergeSort)

（即合并排序）

回答by piccolbo

So merging polygen wit AndreyT we get:

所以将 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)}

I can't claim credit for this one, but it is the most concise and shows the symmetry between the two arguments, doesn't introduce any obscure helper functions. I am not sure an optimizing compiler will see a tail recursion here but I do. The indentation is a final touch.

我不能为这个功劳，但它是最简洁的，显示了两个参数之间的对称性，没有引入任何晦涩的辅助函数。我不确定优化编译器会在这里看到尾递归，但我会。缩进是最后的润色。

回答by herohuyongtao

Use recursion. The code is as follows:

使用递归。代码如下：

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

回答by Abhishek Jadhav

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

回答by Brijesh Valera

I have created recursion function for it. Here is my solution:

我已经为它创建了递归函数。这是我的解决方案：

Node* merge_recursion(Node* l1, Node* l2)
{
        if (!l1)
                return l2;
        if (!l2)
                return l1;

        if (l1->data < l2->data) {
                l1->next = merge_recursion(l1->next, l2);
                return l1;
        } else {
                l2->next = merge_recursion(l1, l2->next);
                return l2;
        }
}

Store return pointer into new pointer variable (in main() / calling function) and traverse linked list on new pointer to print data, it will result sorted merged linked list.

将返回指针存储到新的指针变量中（在 main() / 调用函数中）并在新指针上遍历链表以打印数据，它将产生排序合并链表。

回答by Abhishek Kshirsagar

You can use recursion:

您可以使用递归：

Node* MergeLists(Node *headA, Node* headB)
{

if(headA==NULL){
    return headB;
}else if(headB ==NULL){
    return headA;
}
Node* head = NULL;
if(headA->data <= headB->data){
    head= headA;
    head->next = MergeLists(headA->next,headB);
}else{
    head= headB;
    head->next = MergeLists(headA,headB->next);
}
 return head;
}