两个有序链表进行合并，使合并后的链表也有序
假设链表1:1->3>5
链表2: 2->4->6
合并之后新的链表为：1->2->3->4->5->6
LinkList SortedMerge(LinkedNode* a, LinkedNode* b) { LinkedNode* result = NULL; if(a == NULL) return (b); else if(b == NULL) return (a); if(a->data <= b->data) { result = a; result->next = SortedMerge(a->next, b); } else { result = b; result->next = SortedMerge(a, b->next); } return (result); }
完整程序如下：
#include <stdio.h> #include <malloc.h> typedef int DataType; typedef struct node { DataType data; struct node *next; }LinkedNode, *LinkList; LinkList create_list() { DataType value[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; int len = sizeof(value) / sizeof(DataType); int i = 0; LinkedNode *list_head = NULL; LinkedNode *temp = NULL; LinkedNode *p = NULL; list_head = (LinkedNode*)malloc(sizeof(LinkedNode)); list_head->data = value[0]; list_head->next = NULL; temp = list_head; for(i = 1; i < len; i++) { while (temp->next != NULL) { temp = temp->next; } p = (LinkedNode*)malloc(sizeof(LinkedNode)); p->data = value[i]; p->next = NULL; temp->next = p; } return list_head; } void print(LinkList list) { LinkedNode *temp = NULL; if(list == NULL) return; temp = list; while(temp != NULL) { printf("%d ", temp->data); temp = temp->next; } printf("\n"); return; } LinkList SortedMerge(LinkedNode* a, LinkedNode* b) { LinkedNode* result = NULL; /*Base cases*/ if(a == NULL) return (b); else if(b == NULL) return (a); /*Pick either a or b, and recur */ if(a->data <= b->data) { result = a; result->next = SortedMerge(a->next, b); } else { result = b; result->next = SortedMerge(a, b->next); } return (result); } int main() { LinkList list = NULL; LinkList list2 = NULL; list = create_list(); print(list); list2 = create_list(); print(list2); list=SortedMerge(list,list2); printf("after merge:\n"); print(list); return 0; }
实验结果：
