如何合并已排序的链表

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

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

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