合併兩個排序的列表了運行時錯誤

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