如何合并排序已经排序的链表？

Question

我写了一个合并两个已经排序的链表的方法。然而，由于某种原因，列表的最后一个节点没有打印出来。有什么想法吗？

#include <iostream>
using namespace std;

struct node {
        int number;
        node *next;
        node *prev;
};

    void mergeSort(node*& head, node*& head1);

    int main(int argc, const char * argv[])
    {

//Linked List #1 
        node *head;
        node *tail;
        node *curr;

//1st node
        curr = new node;
        curr-> number = 1;
        curr-> prev = NULL;
        head = curr;
        tail = curr;

        //2nd node
        curr = new node;
        curr-> number = 3;
        curr -> prev = tail;
        tail -> next = curr;
        tail = curr;

        //3rd node
        curr = new node;
        curr-> number = 5;
        curr -> prev = tail;
        tail -> next = curr;
        tail = curr;

        //4th node (tail)
        curr = new node;
        curr-> number = 7;
        curr -> prev = tail;
        tail -> next = curr;
        tail = curr;
        tail->next = NULL;

        //Print Linked List #1
        cout<< "Linked List #1: " << endl;
        curr = head;
        while (curr != NULL){
            cout << curr-> number;
            curr = curr->next;
        }
        cout << endl;

    //Linked List #2
        node *head1;
        node *tail1;
        node *curr1;

        //1st node
        curr1 = new node;
        curr1-> number = 2;
        curr1-> prev = NULL;
        head1 = curr1;
        tail1 = curr1;

        //2nd node
        curr1 = new node;
        curr1-> number = 4;
        curr1 -> prev = tail1;
        tail1 -> next = curr1;
        tail1 = curr1;

        //3rd node
        curr1 = new node;
        curr1-> number = 6;
        curr1 -> prev = tail1;
        tail1 -> next = curr1;
        tail1 = curr1;

        //4th node (tail)
        curr1 = new node;
        curr1-> number = 8;
        curr1 -> prev = tail1;
        tail1 -> next = curr1;
        tail1 = curr1;
        tail1->next = NULL;

        //Print Linked List #2
        cout<< "Linked List #2: " << endl;
        curr1 = head1;
        while (curr1 != NULL){
            cout << curr1-> number;
            curr1 = curr1->next;
        }
        cout << endl;

        //Call MergeSort function
        mergeSort(head, head1);


        return 0;
    }

下面是链接列表的合并排序方法。

    void mergeSort(node*& head, node*& head1){

        //Set up the Merge Sorted Linked List

        node *head2;
        node *tail2;
        node *curr2;

        node *curr = head;
        node *curr1 = head1;

        node* next = curr->next;
        node* next1 = curr1->next;
        node* next2 = curr2->next;

        //1st NODE
        curr2 = new node;

        if (curr->number > curr1->number){
            curr2->number = curr1->number;
            curr1 = curr1->next;
            curr1 = next1;
        }
        else if (curr1->number > curr->number){
            curr2->number = curr->number;
            curr = curr->next;
            curr = next;
        }


        //Set prev of head to Null
        curr2 -> prev = NULL;
        //Set head
        head2 = curr2;
        //Set tail
        tail2 = curr2;



        //BODY NODES
        while (curr != NULL && curr1 != NULL ){
            curr2 = new node;



        //compare the data between the two nodes

            //compare the data between the two nodes
            if (curr1->number >= curr -> number){
                //set the new node's data to the smallest of the previous 
              //node's datas
                //from the other two Linked Lists
                curr2 -> number = curr -> number;

                //link the new node to the previous
                curr2 -> prev = tail2;
                //attach the predecessor node's next pointer to the current         
                //node
                tail2 -> next = curr2;
                //set the new node as the tail
                tail2 = curr2;

                //iterate through the selected Linked List
                curr = curr -> next;



            }


            else if (curr->number >= curr1-> number){
           //set the new node's data to the smallest of the previous node's 
           //datas
            //from the other two Linked Lists
                curr2 -> number = curr1 -> number;

            //link the new node to the previous
                curr2 -> prev = tail2;
            //attach the predecessor node's next pointer to the current node
                tail2 -> next = curr2;
            //set the new node as the tail
                tail2 = curr2;

            //iterate through the selected Linked List
                curr1 = curr1 -> next;

            }


        } tail2 -> next = NULL;



    //Print Linked List #3
            cout<< "Linked List #3: " << endl;
            curr2 = head2;
            while (curr2){
                cout << curr2-> number;
                curr2 = curr2->next;

            }
            cout << endl;

    }

Answer 1

合并函数不应分配节点，而应仅链接现有节点的指针。下面是合并两个单个链接列表的示例。如果您需要以前的指针，可以在执行合并后完成：

NODE * MergeLists(NODE *pSrc1, NODE *pSrc2)
{
NODE *pDst = NULL;                      /* destination head ptr */
NODE **ppDst = &pDst;                   /* ptr to head or prev->next */
    while(1){
        if(pSrc1 == NULL){
            *ppDst = pSrc2;
            break;
        }
        if(pSrc2 == NULL){
            *ppDst = pSrc1;
            break;
        }
        if(pSrc2->data < pSrc1->data){  /* if src2 < src1 */
            *ppDst = pSrc2;
            pSrc2 = *(ppDst = &(pSrc2->next));
            continue;
        } else {                        /* src1 <= src2 */
            *ppDst = pSrc1;
            pSrc1 = *(ppDst = &(pSrc1->next));
            continue;
        }
    }
    return pDst;
}