合併兩個排序的鏈表

02-12

合併兩個排序的鏈表

輸入兩個遞增排序的鏈表，合併這兩個鏈表，並使新的鏈表中的節點依然有序遞增。

思路：

當我們得到兩個鏈表中值較小的頭節點，並把它鏈接到已經合併的鏈表之後，

兩個剩餘鏈表的節點依然有序，遞歸處理。

參考代碼：

root@gt:/home/git/Code# ./a.out 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 root@gt:/home/git/Code# cat merge.c #include <stdio.h>#include <stdlib.h>#include <string.h>typedef struct listNode{ int value; struct listNode* pnext;}ListNode;ListNode* merge(ListNode* p1,ListNode* p2){ ListNode* phead = NULL; if(p1 == NULL) return p2; if(p2 == NULL) return p1; if(p1->value < p2->value) { phead = p1; phead->pnext = merge(p1->pnext,p2); } else { phead = p2; phead->pnext = merge(p1,p2->pnext); } return phead;}int main(){ ListNode* p1head = NULL; ListNode* p2head = NULL; for(int i = 9;i >=0;i--) { ListNode* pnew = (ListNode*)malloc(sizeof(ListNode)); pnew->value = 2 * i + 1; pnew->pnext = p1head; p1head = pnew; } for(int i = 9;i >=0;i--) { ListNode* pnew = (ListNode*)malloc(sizeof(ListNode)); pnew->value = 2 * i; pnew->pnext = p2head; p2head = pnew; } ListNode* pnewHead = merge(p1head,p2head); ListNode* ptmp = pnewHead; while(ptmp != NULL) { printf("%d ",ptmp->value); ptmp = ptmp->pnext; } printf(" "); return 0;}