剑指offer16：输入两个单调递增的链表，合成后的链表满足单调不减规则。

1 题目描述

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

2 思路与方法

　　迭代法：两个链表中较小的头结点作为合并后头结点，之后依次合并两个链表中较小的结点，以此类推，最终合并剩余结点； ListNode* out_list =s->Merge(l1,l4)；

　　递归法：两个链表中较小的头结点作为合并后头结点，递归；（不推荐递归）

3 C++核心代码

3.1 迭代实现

 /*
 struct ListNode {
     int val;
     struct ListNode *next;
     ListNode(int x) :
             val(x), next(NULL) {
     }
 };*/
 class Solution {
 public:
     ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
     {
         ListNode* phead = new ListNode();
         ListNode* list_new = phead;
         while(pHead1 || pHead2){
             if(pHead1==NULL){
                 list_new->next=pHead2;
                 break;
             }
             else if(pHead2==NULL){
                 list_new->next = pHead1;
                 break;
             }
             if((pHead1->val)>(pHead2->val))
             {
                 list_new->next = pHead2;
                 list_new = list_new->next;
                 pHead2=pHead2->next;
             }
             else{
                 list_new->next = pHead1;
                 list_new = list_new->next;
                 pHead1=pHead1->next;
             }
         }
         return phead->next;
     }
 };

3.2 递归实现

 /*
 struct ListNode {
     int val;
     struct ListNode *next;
     ListNode(int x) :
             val(x), next(NULL) {
     }
 };*/
 class Solution {
 public:
     ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
     {
         if (!pHead1)
             return pHead2;
         if (!pHead2)
             return pHead1;

         if (pHead1->val < pHead2->val)
             pHead1->next = Merge(pHead1->next, pHead2);
         else
             pHead2->next = Merge(pHead1, pHead2->next);

         return pHead1->val < pHead2->val ? pHead1 : pHead2;
     }
 };

4 完整代码

 #include <iostream>

 using namespace std;

 struct ListNode {
     int val;
     struct ListNode *next;
     ListNode(int x) : val(x), next(NULL) {}
 };
 class Solution {
 public:
     ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
     {
         ListNode* phead = new ListNode();
         ListNode* list_new = phead;
         while (pHead1 || pHead2){
             if (pHead1 == NULL){
                 list_new->next = pHead2;
                 break;
             }
             else if (pHead2 == NULL){
                 list_new->next = pHead1;
                 break;
             }
             if ((pHead1->val)>(pHead2->val))
             {
                 list_new->next = pHead2;
                 list_new = list_new->next;
                 pHead2 = pHead2->next;
             }
             else{
                 list_new->next = pHead1;
                 list_new = list_new->next;
                 pHead1 = pHead1->next;
             }
         }
         return phead->next;
     }
 };
 int main()
 {
     Solution *s = new Solution();
     //vector<int> v = { 2,4,6,1,3,5,7 };
     ListNode *l1 = new ListNode();
     ListNode *l2 = new ListNode();
     ListNode *l3 = new ListNode();
     ListNode *l4 = new ListNode();
     ListNode *l5 = new ListNode();
     ListNode *l6 = new ListNode();
     ListNode *l7 = new ListNode();
     l1->next = l2;
     l2->next = l3;
     //l3->next = l4;
     l4->next = l5;
     l5->next = l6;
     l6->next = l7;

     ListNode* out_list = s->Merge(l1, l4);
     while (out_list){
         cout << out_list->val << " ";
         out_list = out_list->next;
     }
     cout << endl;

     system("pause");
     return ;
 }

参考资料

https://blog.****.net/ansizhong9191/article/details/80697615