# c&#43;&#43; - 如何合并排序已排序的链表？

``````#include <iostream>
using namespace std;

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

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

node *tail;
node *curr;

//1st node
curr = new node;
curr-> number = 1;
curr-> prev = NULL;
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;

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

node *tail1;
node *curr1;

//1st node
curr1 = new node;
curr1-> number = 2;
curr1-> prev = NULL;
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;

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

//Call MergeSort function

return 0;
}
``````

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

//Set up the Merge Sorted Linked List

node *tail2;
node *curr2;

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

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

}
cout << endl;

}
``````

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

0条回复