无法使用辅助链表合并排序链表

Question

请给出一个简单的问题解决方案。我使用了像 mergesort 这样的算法，但我无法 return 我创建的辅助链表的头部。我看过其他关于堆栈溢出的例子。但是我想知道我的代码哪里有问题。

/**
 * 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 知道顺序，它给出了正确的顺序。我在这里遗漏了一些东西。 None 个列表为 NULL

Answer 1

在您的代码中发现了两个问题。首先应该在两个地方将等于运算符更改为布尔值：

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

Answer 2

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

一些 代码被重复了 。 但一般情况下，不应该。如果当前索引指针（currentPointerl1 和 currentPointerl2）中的任何一个达到 NULL，则无需创建额外的节点。对非 NULL 的当前索引指针（currentPointerl1 或 currentPointerl2）的简单引用必须节省复杂性，即避免最后两个 while 循环。

希望下面的代码能帮助您更好地理解它。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode *head, *tail, *root ;
        ListNode *currentPointerl1 = l1, *currentPointerl2 = l2 ;
        
        int flag = 0 ;    //To check whether head value is initialised or not
        
        while(currentPointerl1 != NULL && currentPointerl2 != NULL){
            
            if(currentPointerl1 -> val > currentPointerl2 -> val){
                root = new ListNode(currentPointerl2 -> val) ;
                currentPointerl2 = currentPointerl2 -> next ;
            }
            else{
                root = new ListNode(currentPointerl1 -> val) ;
                currentPointerl1 = currentPointerl1 -> next ;
            }
            
            if(flag == 0){
                flag = 1 ;
                head = root ;
                tail = head ;
                
            }
            else{
                tail -> next = root ;
                tail = tail -> next ;
            }
        }
        
        if(currentPointerl1 == NULL){
            if(flag == 0){
                flag = 1 ;    //Useless assigning the value
                head = currentPointerl2 ;
            }
            else
                tail -> next = currentPointerl2 ;
        }
        else{
            if(flag == 0){
                flag = 1 ;    //Useless assigning the value
                head = currentPointerl1 ;
            }
            else
                tail -> next = currentPointerl1 ;
        }
            
        return head ;
    }
};

无法使用辅助链表合并排序链表

Not able to merge Sorted Linked Lists using Auxiliary Linked List

c++

algorithm

mergesort

pointers

linked-list