合并链表

合并两个有序链表： 如： [1, 2, 4] [1, 3, 4] 合并之后为[1, 1, 2, 3, 4, 4] /* 节点类型 */ typedef struct node{ int val; struct node *next; }ListNode; /* 函数 */ ListNode *merge2Lists(ListNode *p1, ListNode *p2) { ListNode *pre = new ListNode(-1); ListNode *newlist = pre; while( p1!=NULL && p2!=NULL ) { if( p1->val <= p2->val ) { pre->next = p1; p1 = p1->next; } else { pre->next = p2; p2 = p2->next; } pre = pre->next; } pre->next = p1!=NULL?p1:p2; return newlist->next; } 合并 K 个有序链表： 如： [ [NULL], [-1,0,2,6],[3,6],[NULL] ] 合并之后为： [ -1, 0, 2, 3, 6, 6 ] /* 节点类型 */ struct ListNode{ int val; struct ListNode *next; }; /* 合并两个有序链表 */ struct ListNode *mergeTwoLists(struct ListNode *l1, struct ListNode *l2) { if(NULL==l1 && NULL==l2) return NULL; else if(NULL==l1) return l2; else if(NULL==l2) return l1; struct ListNode *pre = (struct ListNode *)malloc(sizeof(struct ListNode)); struct ListNode *head = pre; while( l1!=NULL && l2!=NULL ) { if(l1->val <= l2->val) { pre->next = l1; l1 = l1->next; } else{ pre->next = l2; l2 = l2->next; } pre = pre->next; } pre->next = l1!=NULL?l1:l2; return head->next; } /* 合并 K 个有序链表 */ /* listsSize 为有序链表的个数 */ struct ListNode *mergeKLists(struct ListNode **lists, int listsSize) { if(listsSize<=0) return NULL; if( 1==listsSize ) return lists[0]; int i, interval=1; while( interval < listsSize ) { for( i=0; i+interval<listsSize; i+=2*interval ) { lists[i] = mergeTwoLists(lists[i], lists[i+interval]); } interval *= 2; } return lists[0]; }