合并两个已排序的列表时出错

Question

以下是我在Leetcode上解决“合并两个排序列表”算法问题的代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode *dummy, *pre;
        dummy->next = l1;
        pre = dummy;
        while(l1 != NULL & l2 != NULL) {
            if(l1->val < l2->val) {
                pre = l1;
                l1 = l1->next;
            } else {
                pre->next = l2;
                l2->next = l1;
                pre = l2;
                l2 = l2->next;
            }
        }
        if(l2 != NULL) {
            pre->next = l2;
        }
        return dummy->next;

    }
};

我得到了一个运行时错误。但是我的代码有什么问题？

Answer 1

代码中的主要问题是您正在使用：

    dummy->next = l1;

当虚拟尚未初始化为指向有效对象时。

您还使用了按位

    while(l1 != NULL & l2 != NULL) {

这里有一个建议的实现。

PS它没有经过测试，但在我看来是正确的。

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {

   ListNode* ret = NULL;
   ListNode* pre = NULL;

   // Make sure the start of the list to be returned points to the right
   // ListNode.
   if ( l1 != NULL && l2 != NULL )
   {
      if ( l1->val < l2->val )
      {
         ret = l1;
         l1 = l1->next;
      }
      else
      {
         ret = l2;
         l2 = l2->next;
      }
   }
   else if ( l1 != NULL )
   {
      return l1;
   }
   else
   {
      return l2;
   }

   pre = ret;

   while(l1 != NULL && l2 != NULL) {

      // Figure out where pre->next must point to.
      // Advance l1 and l2 appropriately.
      if(l1->val < l2->val) {
         pre->next = l1;
         pre = l1;
         l1 = l1->next;
      } else {
         pre->next = l2;
         pre = l2;
         l2 = l2->next;
      }
   }

   // Make sure pre->next points to the remaining ListNodes.
   // They could be in l1 or l2.
   if ( l1 != NULL )
   {
      pre->next = l1;
   }

   if( l2 != NULL)
   {
      pre->next = l2;
   }

   return ret;
}

Answer 2

我认为您得到了分段错误（核心转储），因为您试图访问无效的内存：

dummy->next = l1;

在访问它们的成员之前，您应该将内存分配给*虚拟和*前。

也可以使用

while(l1 != NULL & l2 != NULL) {

与

while(l1 != NULL && l2 != NULL) {

使用new操作符分配内存，请使用delete释放内存并避免内存泄漏。

还要注意，实现本身在逻辑上是错误的。请参阅此处以了解更好的实现。

下面是一个简单的递归实现：

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { 
{
  ListNode* result = NULL;

  /* Base cases */
  if (l1 == NULL) 
     return (l2);
  else if (l2 == NULL) 
     return (l1);

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

Answer 3

我相信一个正确的实现将需要比OP中更多的代码。我假设输入列表l1和l2按降序排序（即从头部到尾部从最大到最小）。

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode *pnt1 = l1;
        ListNode *pnt2 = l2;
        ListNode *head;

        // assign the head pointer to larger head of the two input lists
        if (l1->val > l2->val) {
            head = l1;
        }
        else {
            head = l2;
        }

        // walk through both lists sequentially,
        // and splice together the sorted list
        while (pnt1->next != NULL & pnt2->next != NULL) {
            if(pnt2->val > pnt1->next->val && pnt1->val > pnt2->val) {
                ListNode* next = pnt1->next;
                pnt1->next = pnt2;
                pnt1 = next;
            }
            else if(pnt2->val > pnt1->next->val && pnt1->val <= pnt2->val) {
                ListNode* next = pnt2->next;
                pnt2->next = pnt1;
                pnt2 = next;
            }
            else if(pnt2->val <= pnt1->next->val && pnt1->val > pnt2->val) {
                pnt1 = pnt1->next;
            }
        }

        // handle edge case where end of one or two list(s) has been reached
        if (pnt1->next == NULL && pnt2->next == NULL) {
            if (pnt1->val > pnt2->val) {
                pnt1->next = pnt2;
            }
            else {
                pnt2->next = pnt1;
            }
        }
        else if (pnt1->next == NULL) {
            while (pnt2->next != NULL) {
                if (pnt1->val > pnt2->next->val) {
                    ListNode* next = pnt2->next;
                    pnt2->next = pnt1;
                    pnt1->next = next;
                    break;
                }
                pnt2 = pnt2->next;
            }
            if (pnt2->next == NULL) {
                pnt2->next = pnt1;
            }
        }
        else if (pnt2->next == NULL) {
            while (pnt1->next != NULL) {
                if (pnt2->val > pnt1->next->val) {
                    ListNode* next = pnt1->next;
                    pnt1->next = pnt2;
                    pnt2->next = next;
                    break;
                }
                pnt1 = pnt1->next;
            }
            if (pnt1->next == NULL) {
                pnt1->next = pnt2;
            }
        }

        return head;
    }
};