以下合併排序數組C++代碼有什麼問題？

我一直在C++中實現合併排序的數組問題，並發現我的代碼中發生了一些奇怪的事情。所以，這是我的代碼。以下合併排序數組C++代碼有什麼問題？

#include <iostream> 
using namespace std; 

struct ListNode { 
    int val; 
    ListNode *next; 
    ListNode(int x): val(x), next(NULL) {} 
}; 

class Solution { 
public: 
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) { 
     if (l1 == NULL) 
      return l2; 
     else if (l2 == NULL) 
      return l1; 
     else 
     { 
      ListNode *head, *p; 
      ListNode *h1 = l1; 
      ListNode *h2 = l2; 
      if (h1->val <= h2->val) 
      { 
       ListNode newNode(h1->val); 
       head = &newNode; 
       h1 = h1->next; 
      } 
      else 
      { 
       ListNode newNode(h2->val); 
       head = &newNode; 
       h2 = h2->next; 
      } 
      p = head; 
      while (h1 != NULL && h2 != NULL) 
      { 
       if (h1->val <= h2->val) 
       { 
        ListNode *Node = new ListNode(h1->val); 
        p->next = Node; 
        //p = p->next; 
        h1 = h1->next; 
       } 
       else 
       { 
        ListNode *Node = new ListNode(h2->val); 
        p->next = Node; 
        //p = p->next; 
        h2 = h2->next; 
       } 
       p = p->next; 
      } 
      if (h2 != NULL) 
      { 
       while (h2 != NULL) 
       { 
        ListNode *Node = new ListNode(h2->val); 
        p->next = Node; 
        p = p->next; 
        h2 = h2->next; 
       } 
      } 
      else if (h1 != NULL) 
      { 
       while (h1 != NULL) 
       { 
        ListNode *Node = new ListNode(h1->val); 
        p->next = Node; 
        p = p->next; 
        h1 = h1->next; 
       } 
      } 
      return head; 
     } 
    } 
}; 

int main() 
{ 
    ListNode A1(1); 
    ListNode A2(2); 
    ListNode A3(3); 
    ListNode A4(5); 
    ListNode A5(7); 
    A1.next = &A2; 
    A2.next = &A3; 
    A3.next = &A4; 
    A4.next = &A5; 
    ListNode B1(2); 
    ListNode B2(4); 
    ListNode B3(6); 
    ListNode B4(8); 
    ListNode B5(10); 
    B1.next = &B2; 
    B2.next = &B3; 
    B3.next = &B4; 
    B4.next = &B5; 
    Solution solution; 
    ListNode *x = solution.mergeTwoLists(&A1, &B1); 
    while (x != NULL) 
    { 
     cout << x->val << endl; 
     x = x->next; 
    } 
    return 0; 
}

此代碼將得到一個運行時錯誤。當我在代碼塊中調試它時，我發現類Solution中的所有東西都是正常的。當涉及到main函數時，while循環發生了異常情況！ x在一個循環後指向一些奇怪的地址。我想知道什麼是錯的。

來源

2014-12-05 user3162587

嘗試使用此

while (x->next != NULL)

來源

2014-12-05 05:55:53

在這裏，mergeTwoLists：

if (h1->val <= h2->val) 
    { 
     ListNode newNode(h1->val); 
     head = &newNode; 
     h1 = h1->next; 
    } 
    else 
    { 
     ListNode newNode(h2->val); 
     head = &newNode; 
     h2 = h2->next; 
    }

所有你與new堆上創建的其他節點的，但在這裏你在棧上創建newNode。它是您正在構建的列表的第一個節點，它是一個局部變量mergeTwoLists。當控制超出函數時，該第一個節點超出範圍。然後，您訪問它並取消中的next，這是未定義的行爲。

來源

2014-12-05 06:12:57 Beta

的第一個問題我看到聯合國怨婦代碼爲您保留地址，以堆棧分配的變量：

ListNode *head, *p; 
// ... 
if (h1->val <= h2->val) { 
    ListNode newNode(h1->val); 
    head = &newNode; 
    h1 = h1->next; 
    // newNode is destroyed here 
    // thus head now points to invalid 
    // data 
} else { 
    // same kind of code 
} 
p = head; 
// p does not point to anything useful

這是什麼地方錯了你的代碼。

像您正在實施的鏈接列表ListNode通常使用動態分配的節點實現。你也應該在這裏嘗試。我建議你在合併之前爲你的鏈表實現最基本的算法（插入，刪除，搜索），這樣你就更有可能摸索這個結構。

來源

2014-12-05 06:31:02 Julien

以下合併排序數組C++代碼有什麼問題？

回答

相關問題