合并两个有序链表--链表的递归处理

0x01.问题

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
输入示例：1->2->4, 1->3->4
输出示例：1->1->2->3->4->4

C++结构体为：
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
 C++函数形式为  ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) 

0x02.简要分析

题目很简单，两个链表都是有序的，所以我们只要从两个链表种，依次拿出一个值来比较，小的放入新链表，指针后移一位，当两个有一个为空时，再把另一个全部放到新链表的尾部。

这种问题其实也可以用递归来解决，利用函数返回 l1 指向的结点和 l2 指向的结点中，值较小的结点，并将从下级函数获得的返回值，链接到当前结点尾部，当 l1为空，或 l2 为空，函数结束，然后再返回回 l1 或 l2 中剩下的部分。

需要注意的地方有：

• 这个传入的结点已经是有数据的了，从示例可以看出。
• 非递归情况下，可以用哑节点省去步必要的判断。

0x03.解决代码–原始非递归

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(!l1) return l2;
        if(!l2) return l1;
        ListNode*p1=l1;
        ListNode*p2=l2;
        ListNode*result=new ListNode(0);
        ListNode*p3=result;
        while(p1&&p2){
            if(p1->val<p2->val){
                p3->val=p1->val;
                p1=p1->next;
            }
            else{
                p3->val=p2->val;
                p2=p2->next;
            }
            if(p1&&p2){
                p3->next=new ListNode(0);
                p3=p3->next;
            }
        }
        while(p1){
            p3->next=new ListNode(0);
            p3=p3->next;
            p3->val=p1->val;
            p1=p1->next;
        }
        while(p2){
            p3->next=new ListNode(0);
            p3=p3->next;
            p3->val=p2->val;
            p2=p2->next;
        }
        return result;
    }
};

这个解决代码其实很是复杂了，解决的思路是建立一个新的链表，然后不断进行值得传递，这种方法其实已经失去了链表得本质，为什么要传递值呢？链表本来就由一个个节点组成，这个节点本身就是可以传递的了，只要考虑下指向方向就行了，所以没必要每次都new出一个新的节点。

0x04.解决代码–最简非递归

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode*head=new ListNode(0);
        ListNode*temp=head;
        while(l1&&l2){
            if(l1->val<l2->val){
                head->next=l1;
                l1=l1->next;
            }
            else{
                head->next=l2;
                l2=l2->next;
            }
            head=head->next;
        }
        head->next= (l1==NULL)?l2:l1;
        return temp->next;
    }
};

0x05.解决代码–递归

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(!l1) return l2;
        if(!l2) return l1;
        if(l1->val<=l2->val){
            l1->next=mergeTwoLists(l1->next,l2);
            return l1;
        }
        l2->next=mergeTwoLists(l1,l2->next);
        return l2;
    }
};

ATFWUS --Writing By 2020–03–23