Невозможно объединить Сортированные связанные списки с использованием вспомогательного связанного списка

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