合并两个排序的列表了运行时错误

Question

这里是我的代码对本文给出了“合并两个排序列表”算法的问题：

/** 
* 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

我觉得你有Segmentation Fault(Core Dump)因为你试图访问是无效的内存：

dummy->next = l1; 

你应该访问他们的成员之前分配内存的*dummy和*pre。

还在循环中使用&&（逻辑运算符）而不是&（按位运算符）。替换：

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

与

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

使用new运营商来分配内存，并请使用delete释放相同，避免内存泄漏。

另请注意，执行本身是故障通过逻辑。请参阅here以获得更好的实现。

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

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 2

我认为，正确的实施将需要多得多的代码比你在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; 
    } 
}; 

Answer 3

在你的代码的主要问题是，你正在使用：

dummy->next = l1; 

时dummy尚未初始化指向一个有效的对象。

您还正在使用按位&，其中逻辑&&是合适的。

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 4

除了问题已经指出的，原来的代码不处理，其中先达到列表2的端部的情况下，在这种情况下，列表1的其余部分应被附加到合并的名单。使用指向指针的指针（而不是以前的指针）使代码更简单。以下是合并两个列表的示例代码，以及使用合并列表功能的自底向上合并排序。该排序使用指向列表的指针数组，其中array [i]为null或指向列表中包含pow（2，i）元素的列表。

ListNode * MergeLists(ListNode *pl1, ListNode *pl2) 
{ 
ListNode *plm = NULL;     /* merged list head ptr */ 
ListNode **pplm = &plm;     /* ptr to head or prev->next */ 
    if(pl1 == NULL) 
     return pl2; 
    if(pl2 == NULL) 
     return pl1; 
    while(1){ 
     if(pl2->val < pl1->val){  /* if src2 < src1 */ 
      *pplm = pl2; 
      pl2 = *(pplm = &(pl2->next)); 
      if(pl2 == NULL){ 
       *pplm = pl1; 
       break; 
      } 
     } else {      /* src1 <= src2 */ 
      *pplm = pl1; 
      pl1 = *(pplm = &(pl1->next)); 
      if(pl1 == NULL){ 
       *pplm = pl2; 
       break; 
      } 
     } 
    } 
    return plm; 
} 

#define NUMLISTS 32      /* number of lists */ 
ListNode * SortList(ListNode *pList) 
{ 
ListNode * aList[NUMLISTS];    /* array of lists */ 
ListNode * pNode; 
ListNode * pNext; 
int i; 
    if(pList == NULL)     /* check for empty list */ 
     return NULL; 
    for(i = 0; i < NUMLISTS; i++)  /* zero array */ 
     aList[i] = NULL; 
    pNode = pList;      /* merge nodes into aList[] */ 
    while(pNode != NULL){ 
     pNext = pNode->next; 
     pNode->next = NULL; 
     for(i = 0; (i < NUMLISTS) && (aList[i] != NULL); i++){ 
      pNode = MergeLists(aList[i], pNode); 
      aList[i] = NULL; 
     } 
     if(i == NUMLISTS) 
      i--; 
     aList[i] = pNode; 
     pNode = pNext; 
    } 
    pNode = NULL;      /* merge array into one list */ 
    for(i = 0; i < NUMLISTS; i++) 
     pNode = MergeLists(aList[i], pNode); 
    return pNode; 
}