[剑指Offer] 16.合并两个排序链表

题目描述

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

【思路1】递归

 1 /*
 2 struct ListNode {
 3     int val;
 4     struct ListNode *next;
 5     ListNode(int x) :
 6             val(x), next(NULL) {
 7     }
 8 };*/
 9 class Solution {
10 public:
11     ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
12     {
13         if(pHead1 == NULL)
14             return pHead2;
15         else if(pHead2 == NULL)
16             return pHead1;
17         ListNode* res = NULL;
18         if(pHead1->val <= pHead2->val){
19             res = pHead1;
20             res->next = Merge(pHead1->next, pHead2);
21         }else{
22             res = pHead2;
23             res->next = Merge(pHead1,pHead2->next);
24         }
25         return res;
26     }
27 };

【思路2】非递归，新建一个链表并保存头结点，将原来两个链表进行比较按顺序插入到新链表中，最后将有剩余的链表直接接上。

 1 /*
 2 struct ListNode {
 3     int val;
 4     struct ListNode *next;
 5     ListNode(int x) :
 6             val(x), next(NULL) {
 7     }
 8 };*/
 9 class Solution {
10 public:
11     ListNode* Merge(ListNode* pHead1, ListNode* pHead2){
12         if(pHead1 == NULL)
13             return pHead2;
14         else if(pHead2 == NULL)
15             return pHead1;
16         ListNode* res = NULL;
17         ListNode* cur = NULL;
18         while(pHead1 != NULL && pHead2 != NULL){
19             if(pHead1->val <= pHead2->val){
20                 if(res == NULL)
21                     res = cur = pHead1;
22                 else{
23                     cur->next = pHead1;
24                     cur = cur->next;
25                 }
26                 pHead1 = pHead1->next;
27             }else{
28                 if(res == NULL)
29                     res = cur = pHead2;
30                 else{
31                     cur->next = pHead2;
32                     cur = cur->next;
33                 }
34                 pHead2 = pHead2->next;
35             }
36         }
37         if(pHead1 == NULL){
38             cur->next = pHead2;
39         }
40         if(pHead2 == NULL){
41             cur->next = pHead1;
42         }
43         return res;
44     }
45 };