算法与数据结构（合并有序链表）

思路：

本题可以用迭代或递归两种方法来解题：

本次的方法为递归，通过不断来移动链表中元素的位置实现递归

解题过程：

L1: 1   2   4

L2: 1   3   4

首先判断两个链表都不为空，所以前两个条件不符合

接着判断list1->val以及list2->val的大小

（1）若list1->val < list2->val

则说明L1应该在L2的前面，所以进行递归

（2）如果list1->val >= list2->val,则执行以下操作

递归的详细步骤：

第一步：首先比较list1的1和list2的1

执行（2）

返回了list2,直接确定了文件的头，因为确定了文件的头为list2的第一个数字，则list2的数字向后移一个单位

返回的链表：1

第二步：比较list1的1和list2的3

执行（1）

返回了list1，则上一个list2->next = list1

返回的链表： 1->1

第三步：比较list1的2和list2的3

执行（1）

返回了list1，则上一个list1->next = list1

返回的链表： 1->1->2

第四步：比较list1的4和list2的3

执行（2）

返回了list2，则上一个list1->next = list2

返回的链表： 1->1->2->3

第五步：比较list1的4和list2的4

执行（2）

返回了list2，则上一个list2->next = list2

返回的链表： 1->1->2->3->4

第六步：检测到list2为空

则直接返回list1

则上一个list2->next = list1

返回的链表： 1->1->2->3->4->4

代码：

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