【LC_Lesson7】---将两个有序链表合成新的一个有序链表

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

太久没复习数据结构和C/C++的链表实现了，一时间感觉无从下手头蒙了半天，花了半天时间整理了下单链表的基本知识，同时整理了下单链表的前序插入和后续插入。如下链接

https://www.cnblogs.com/szhb-5251/p/11770322.html

一. 解题思路

思路一：

1) 两个链表均是有序的，而且各个节点也都是实际存在的，可以考虑重新拉一个链表出来，然后依次扫描两个有序链表，有序的将元素分别插入在新链表上面。一直到某条链表扫描结束，然后把另外一条链表剩余的元素插入在当前新链表的后面即可。

C++实现：

 1 class Solution {
 2 public:
 3     ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
 4         if(l1 == NULL) 
 5             return l2;
 6         if(l2 == NULL)
 7             return l1;
 8         ListNode *p = l1;
 9         ListNode *q = l2;
10         ListNode *result = new ListNode(0);
11         ListNode *r = result;
12 
13         while(q && p)
14         {
15             if (q->val < p->val)
16             {
17                 r->next = q;
18                 r = r->next;
19                 q = q->next;
20             }
21             else
22             {
23                 r->next = p;
24                 r = r->next;
25                 p = p->next;
26             }
27         }
28         if (q)
29             r->next = q;
30         if (p)
31             r->next = p;  
32         return result->next;
33     }
34 };

思路二：

　　其次可以使用递归的方法，