// 合并链表.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include<iostream>
using namespace std;
//单向有序链表合并
/*
typedef struct NodeType
{
int val;
NodeType *next;
}Node;
Node* MergeList(Node *h1, Node *h2)
{
if (NULL == h1 || NULL == h2)
return h1;
if (NULL == h1->next)
return h2;
if (NULL == h2->next)
return h1;
Node *curr1, *curr2, *prev1, *temp;
prev1 = h1;
curr1 = h1->next;
curr2 = h2->next;
temp = h2;
while (curr2)
{
while (curr1!=NULL&&curr1->val>curr2->val)
{
prev1 = curr1;
curr1 = curr1->next;
}
temp = curr2->next;
prev1->next = curr2;
curr2->next = curr1;
//curr1=curr2;
curr2 = temp;
}
return h1;
}*/
//双向有序链表合并
typedef struct DnodeType
{
int val;
DnodeType *prev;
DnodeType *next;
}Dnode;
Dnode* MergeList(Dnode *h1, Dnode *h2)
{
if (NULL == h1 || NULL == h2)
return h1;
if (NULL == h1->next)
return h2;
if (NULL == h2->next)
return h1;
Dnode *curr1, *curr2, *temp, *prev1;
prev1 = h1;
curr1 = h1->next;
curr2 = h2->next;
temp = h2;
while (curr2)
{
while (curr1!=NULL&&curr1->val > curr2->val)
{
prev1 = curr1;
curr1 = curr1->next;
}
temp = curr2->next;
prev1->next = curr2;
curr2->prev = prev1;
if (curr1 == NULL)
curr2->next = NULL;
else
{
curr2->next = curr1;
curr1->prev = curr2;
}
curr2 = temp;
}
return h1;
}
int main()
{
Dnode *head1 = NULL;
Dnode *node1 = NULL, *node2 = NULL, *node3 = NULL, *node4 = NULL;
head1 = (Dnode *)malloc(sizeof(Dnode));
node1 = (Dnode *)malloc(sizeof(Dnode));
node2 = (Dnode *)malloc(sizeof(Dnode));
node3 = (Dnode *)malloc(sizeof(Dnode));
node4 = (Dnode *)malloc(sizeof(Dnode));
node1->val = 8;
node2->val = 6;
node3->val = 4;
node4->val = 2;
head1->next = node1;
node1->prev = head1;
node1->next = node2;
node2->prev = node1;
node2->next = node3;
node3->prev = node2;
node3->next = node4;
node4->prev = node3;
node4->next = NULL;
Dnode *head2 = NULL;
Dnode *node5 = NULL, *node6 = NULL, *node7 = NULL, *node8 = NULL;
head2 = (Dnode *)malloc(sizeof(Dnode));
node5 = (Dnode *)malloc(sizeof(Dnode));
node6 = (Dnode *)malloc(sizeof(Dnode));
node7 = (Dnode *)malloc(sizeof(Dnode));
node8 = (Dnode *)malloc(sizeof(Dnode));
node5->val = 7;
node6->val = 5;
node7->val = 3;
node8->val = 1;
head2->next = node5;
node5->prev = head2;
node5->next = node6;
node6->prev = node5;
node6->next = node7;
node7->prev = node6;
node7->next = node8;
node8->prev = node7;
node8->next = NULL;
Dnode *ptr;
ptr=MergeList(head1, head2);
ptr = ptr->next;
while (ptr != NULL)
{
printf("%d\n", ptr->val);
ptr = ptr->next;
}
}
/*
int main()
{
Node *head1 = NULL;
Node *node1 = NULL, *node2 = NULL, *node3 = NULL, *node4 = NULL;
head1 = (Node *)malloc(sizeof(Node));
node1 = (Node *)malloc(sizeof(Node));
node2 = (Node *)malloc(sizeof(Node));
node3 = (Node *)malloc(sizeof(Node));
node4 = (Node *)malloc(sizeof(Node));
node1->val = 8;
node2->val = 6;
node3->val = 4;
node4->val = 2;
head1->next = node1;
node1->next = node2;
node2->next = node3;
node3->next = node4;
node4->next = NULL;
Node *head2 = NULL;
Node *node5 = NULL, *node6 = NULL, *node7 = NULL, *node8 = NULL;
head2 = (Node *)malloc(sizeof(Node));
node5 = (Node *)malloc(sizeof(Node));
node6 = (Node *)malloc(sizeof(Node));
node7 = (Node *)malloc(sizeof(Node));
node8 = (Node *)malloc(sizeof(Node));
node5->val = 7;
node6->val = 5;
node7->val = 3;
node8->val = 1;
head2->next = node5;
node5->next = node6;
node6->next = node7;
node7->next = node8;
node8->next = NULL;
Node *ptr;
ptr = MergeList(head1, head2);
ptr = ptr->next;
while (ptr != NULL)
{
printf("%d\n", ptr->val);
ptr = ptr->next;
}
}*/
