本文共 1156 字，大约阅读时间需要 3 分钟。
题目：
输入两个递增排序的链表，合并这两个链表并使新链表仍然是按照递增排序的。
边界条件：
两个空链表，一个空链表。两个链表只有一个结点。存在值相等的多个链表。
注意资源的回收。
思路：
用递归来做。
时间复杂度：O（min(n1,n2)）
#include#include #include #include #include using namespace std;struct ListNode{ int value; ListNode *next; ListNode(int a){ value = a; next = NULL; }};ListNode *MergeList(ListNode *head1,ListNode *head2){ if (head1 == NULL) return head2; if (head2 == NULL) return head1; ListNode *newHead = NULL; if (head1->value <= head2->value) { newHead = head1; newHead->next = MergeList(head1->next, head2); } else { newHead = head2; newHead->next = MergeList(head1, head2->next); } return newHead;}int main(){ ListNode *a1 = new ListNode(1); ListNode *a2 = new ListNode(3); ListNode *a3 = new ListNode(5); ListNode *a4 = new ListNode(7); ListNode *a5 = new ListNode(9); a1->next = a2; a2->next = a3; a3->next = a4; a4->next = a5; ListNode *b1 = new ListNode(2); ListNode *b2 = new ListNode(4); ListNode *b3 = new ListNode(6); b1->next = b2; b2->next = b3; ListNode *re = MergeList(a1,b1); for (; re != NULL; re = re->next) cout << re->value << " "; cout << endl; return 0;}
转载地址：http://tapmi.baihongyu.com/