合并两个有序链表
问题描述：
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = [] 输出：[]
示例 3：
输入：l1 = [], l2 = [0] 输出：[0]
思路：
类比数组的合并，比较两个链表之前元素的大小，将其归纳到另一个链表。
目录
问题描述：
解决代码：
代码解析：
1.
2.
3.
4.
需要注意的是，当完成遍历之后，此时cur2有可能时NULL！
5.
需要注意的是
6.
ps：
解决代码：
以list2为主体，将list1合并到list2
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
struct ListNode* cur1 = list1;
struct ListNode* cur2 = list2;
struct ListNode* prev = NULL; //不可以放在循环内部，否则会出现空指针问题
while(cur1 && cur2){
if(cur1->val <= cur2->val){
if(cur2 == list2){
list1 = cur1->next;
cur1->next = cur2;
cur2 = cur1;
cur1 = list1;
list2 = cur2;
}
else{
list1 = cur1->next;
cur1->next = cur2;
prev->next = cur1;
prev = cur1;
cur1 = list1;
}
}
else{
prev = cur2;
cur2 = cur2->next;
}
}
//此时cur2已经是NULL，不能以用cur2
//prev本身初始化时就是NULL！所以需要判断！ cur1若全部添加到cur2之后，那么cur1也是NULL，所以cur1也需要断言。
//判断要写在解引用语句之前！如果已经去解引用了，那么判断将无意义！
if(cur1 && prev && prev->val < cur1->val) //如果list2遍历结束，都找出不大于cur1->val的值
prev->next = cur1;
if(list2) //注意是否为空！
return list2;
else
return list1;
}代码解析：
1.
struct ListNode* cur1 = list1;
struct ListNode* cur2 = list2;
struct ListNode* prev = NULL; //不可以放在循环内部，否则会出现空指针问题
既然要遍历整个链表，那就要建立cur指针，不断往下移动，从而完成遍历。
对于链表的链接，需要一个prev指针，将链表的上一个节点与下一个节点链接。
2.
if(cur1->val <= cur2->val){
if(cur2 == list2){
list1 = cur1->next;
cur1->next = cur2;
cur2 = cur1;
cur1 = list1;
list2 = cur2;
}
在小于等于的前提下，当cur2从list2开始的时候，此时需要给list2“换头”。即需要把head1的元素整合到list2头部，所以要 list2 = cur2;
3.
else{
list1 = cur1->next;
cur1->next = cur2;
prev->next = cur1;
prev = cur1;
cur1 = list1;
}
当完成换头之后，此时只需要将list1中的节点连接到list2中。
4.
else{
prev = cur2;
cur2 = cur2->next;
}
这段代码表示，当无法满足 if(cur1->val <= cur2->val)时，需要让cur2往下遍历，找到满足if语句的节点。
需要注意的是，当完成遍历之后，此时cur2有可能时NULL！
5.
if(cur1 && prev && prev->val < cur1->val) //如果list2遍历结束，都找出不大于cur1->val的值
prev->next = cur1;
我们的思路是让cur2不断往下遍历，但是若最后的节点的val仍然小于cur1的val，此时cur1并没有完成遍历，只需要让cur1剩下的元素，连接到cur2尾部即可。
需要注意的是
cur1 && prev 该判断语句必须要添加，并且需要写在if语句的前半部分！
//判断要写在解引用语句之前！ 如果已经去解引用了，那么判断将无意义！
原因：①prev初始化时为NULL，所以要让prev进行判断
②需要判断cur1有没有走到最后的NULL指针。
③需要用prev->val 而不是 cur2->val，此时cur2已经跳出while循环，说明cur2已经是空指针！
6.
if(list2) //注意是否为空！
return list2;
else
return list1;
}
最后，当list2本身为空的，则需要返回list1
ps：
通过刷leetcode可知，leetcode的题目往往会给出很抽象的数据范围，链表本身就可能是空链表！！！