#include <stdio.h> #include <stdlib.h> typedef struct _Node { int data; _Node* next; }Node, *LinkList; bool CreateList(LinkList &head, const int *data, const int len) { Node *cur = NULL; Node *next = NULL; int i; cur = (LinkList)malloc(sizeof(Node)); if(cur == NULL) { return false; } cur->data = data[0]; cur->next = NULL; head = cur; for(i=1; i<len; i++) { next = (LinkList)malloc(sizeof(Node)); if(next == NULL) { return false; } next->data = data[i]; next->next = NULL; cur->next = next; cur = cur->next; } return true; } void PrintList(LinkList head) { while(head != NULL) { printf(" %d", head->data); head = head->next; } } //一般合并 LinkList MergeList(LinkList head1, LinkList head2) { if (head1 == NULL) { return head2; } if (head2 == NULL) { return head1; } LinkList head = NULL; LinkList p1 = NULL; LinkList p2 = NULL; if ( head1->data < head2->data ) { head = head1; p1 = head1->next; p2 = head2; } else { head = head2; p2 = head2->next; p1 = head1; } LinkList cur = head; while ( (p1!=NULL) && (p2!=NULL) ) { if ( p1->data <= p2->data ) { cur->next = p1; cur = p1; p1 = p1->next; } else { cur->next = p2; cur = p2; p2 = p2->next; } } if(p1 != NULL ) { cur->next = p1; if(p2 != NULL) { cur->next = p2; } return head; } } //递归合并 LinkList RMergeList(LinkList head1, LinkList head2) { if(head1 == NULL) { return head2; } if(head2 == NULL) { return head1; } LinkList head = NULL; if (head1->data < head2->data) { head = head1; head->next = RMergeList(head1->next, head2); } else { head = head2; head->next = RMergeList(head1, head2->next); } return head; } void main() { int data1[] = {1, 2, 3, 5}; int len1 = sizeof(data1)/sizeof(int); int data2[] = {2, 4, 6}; int len2 = sizeof(data2)/sizeof(int); LinkList head; LinkList head1; LinkList head2; if( !CreateList(head1, data1, len1) ) { printf("创建链表失败!\n"); return; } if( !CreateList(head2, data2, len2) ) { printf("创建链表失败!\n"); return; } printf("链表1:"); PrintList(head1); printf("\n"); printf("链表2:"); PrintList(head2); printf("\n"); head = MergeList(head1, head2); printf("一般合并:"); PrintList(head); printf("\n"); if( !CreateList(head1, data1, len1) ) { printf("创建链表失败!\n"); return; } if(!CreateList(head2, data2, len2) ) { printf("创建链表失败!\n"); return; } printf("链表1:"); PrintList(head1); printf("\n"); printf("链表2:"); PrintList(head2); printf("\n"); head = RMergeList(head1, head2); printf("递归合并:"); PrintList(head); printf("\n"); }