無法使用輔助鏈接列表合併排序的鏈接列表

Question

請給出一個簡單的問題解決方案。我已經使用了像mergesort這樣的算法，但我無法返回我創建的輔助鏈接列表的頭部。我已經看到了堆棧溢出的其他例子。但我想知道我的代碼問題在哪裏。

/** 
* Definition for singly-linked list. 
* struct ListNode { 
*  int val; 
*  ListNode *next; 
*  ListNode(int x) : val(x), next(NULL) {} 
* }; 
*/ 
ListNode* Solution::mergeTwoLists(ListNode* A, ListNode* B) { 

    ListNode* head; 
    ListNode* root; 

    ListNode* H1 = A; 
    ListNode* H2 = B; 
    int flag = 0; 
    while (H1 != NULL && H2 != NULL){ 
     if(H1->val < H2->val){ 
      root = new ListNode(H1->val); 
      //cout << root->val << " "; 
      if (flag = 0){ 
       head = root; 
       flag = 1; 
      } 

      //root->next = el; 
      root = root->next; 
      H1 = H1->next; 
     }else{ 
      root = new ListNode(H2->val); 
      if (flag = 0){ 
       head =root; 
       flag = 1; 
      } 
      //cout << root->val << " "; 
      //root->next = el; 
      root = root->next; 
      H2 = H2->next; 
     } 
    } 
    while (H2 != NULL){ 

     root = new ListNode(H2->val); 
     //cout << root->val << " "; 
     //root->next = el; 
     root = root->next; 
     H2 = H2->next; 
    } 
    while (H1 != NULL){ 
     root = new ListNode(H1->val); 
     //cout << root->val << " "; 
     //root->next = el; 
     root = root->next; 
     H1 = H1->next; 
    } 

    ListNode *start=head; 
     while(start) 
      { 
      cout<<start->val<<" "; 
      start=start->next; 
      } 


    return head; 
} 

我已經使用cout知道順序，它給出了正確的順序。我在這裏錯過了一些東西。沒有列表爲NULL

Answer 1

/** 
* Definition for singly-linked list. 
* struct ListNode { 
*  int val; 
*  ListNode *next; 
*  ListNode(int x) : val(x), next(NULL) {} 
* }; 
*/ 
ListNode* Solution::mergeTwoLists(ListNode* A, ListNode* B) { 
     if (A == NULL){ 
     return B; 
     } 
     if (B == NULL){ 
      return A; 
     } 

    ListNode* head; 
    ListNode* root = new ListNode(0); //initialized root 
    ListNode* H1 = A; 
    ListNode* H2 = B; 
    if(H1->val < H2->val){ 
      root->val = H1->val; 
      head = root; 
      H1 = H1->next; 
     }else{ 
      root->val = H2->val; 
      head = root; 
      H2 = H2->next; 
     } 


    while (H1 != NULL && H2 != NULL){ 
     if(H1->val < H2->val){ 
      root->next = new ListNode(H1->val); 
      root = root->next;   //making list 
      H1 = H1->next; 
     }else{ 
      root->next = new ListNode(H2->val); 
      root = root->next; 
      H2 = H2->next; 
     } 
    } 
    while (H2 != NULL){ 
     root->next = new ListNode(H2->val); 
     root = root->next; 
     H2 = H2->next; 
    } 
    while (H1 != NULL){ 
     root->next = new ListNode(H1->val); 
     root = root->next; 
     H1 = H1->next; 
    } 



    return head; 
} 

初始化是沒有做好

Answer 2

在您的代碼中發現兩個問題。 起初等於運營商應改爲布爾在兩個地方：

if (flag = 0){ 

應該

if (flag == 0){ 

然後，尾節點應該在遍歷兩個列表保持。

我轉換在這裏面工作的代碼（應用的最小變動）：

ListNode* mergeTwoLists(ListNode* A, ListNode* B) { 

    ListNode* head; 
    ListNode* tail; //<-- a tail is introduced 
    ListNode* root; 

    ListNode* H1 = A; 
    ListNode* H2 = B; 
    int flag = 0; 
    while (H1 != NULL && H2 != NULL){ 
     if(H1->val < H2->val){ 
      root = new ListNode(H1->val); 
      //cout << root->val << " "; 
      if (flag == 0){ //<-- fixed 
       head = root; 
       tail=head; 
       flag = 1; 
      } 
      else 
      { 
       tail->next=root; 
       tail = root; 
      } 


      //root->next = el; 
      //root = root->next; 
      H1 = H1->next; 
     }else{ 
      root = new ListNode(H2->val); 
      if (flag == 0){ //<-- fixed 
       head =root; 
       tail=head; 
       flag = 1; 
      } 
      else 
      { 
       tail->next=root; 
       tail = root; 
      } 
      //cout << root->val << " "; 
      //root->next = el; 
      // root = root->next; 
      H2 = H2->next; 
     } 
    } 
    while (H2 != NULL){ 

     root = new ListNode(H2->val); 
     //cout << root->val << " "; 
     //root->next = el; 
     tail->next=root; 
     tail=root; 
     // root = root->next; 
     H2 = H2->next; 
    } 
    while (H1 != NULL){ 
     root = new ListNode(H1->val); 
     //cout << root->val << " "; 
     //root->next = el; 
     tail->next=root; 
     tail=root; 
     //root = root->next; 
     H1 = H1->next; 
    } 

    ListNode *start=head; 
     while(start) 
      { 
      cout<<start->val<<" "; 
      start=start->next; 
      } 


    return head; 
}