[数据结构与算法]LeetCode-21.合并两个有序链表

21.合并两个有序单链表：

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

示例 2：

输入：l1 = [], l2 = []
输出：[]
示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

提示：

两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列

思路：

这是一道简单的题目，最优的方法是用递归解决。在这里贴出两种方法来参考：

1. 非递归：

struct ListNode* mergeTwoLists(struct ListNode* l1,struct ListNode* l2){
	struct ListNode *Head=(struct ListNode*)malloc(sizeof(struct ListNode));              //新建一个链表，分配头结点
	struct ListNode *Tail=Head; //尾指针初始指向头结点
	while(l1&&l2){              //循环条件为l1,l2不为空
		if(l1->val<l2->Val){
			Tail->next=l1;      //头结点连接小的元素
			l1=l1->next;        //依次遍历l1每一个结点
		}
		else{
			Tail->next=l2;      
			l2=l2->next;
		}
		Tail=Tail->next;        //尾指针永远指向当前的最后结点
	}
	if(l1)                      //l2先为空时，尾结点后面直接连接l1
		Tail->next=l1;
	else
		Tail->next=l2;
	return Head->next;          //建立的链表为带头结点的单链表，输出时要跳过头结点
}

非递归的方法虽然代码冗长，但是思路清晰便于理解。核心思想是建立两个指针，注意尾指针要一直指向当前的最后一个结点。运用最基本的判断语句来选择l1 l2中较小者做为下一个结点。
还需考虑两个链表长度不一致时，需要在循环外加一个if判断是哪一个先为空，再将另一个链表直接连在当前尾结点后。

2.递归：
由于我的递归也没有学好，所以直接贴出Leetcode官方标答：
“如果 l1 或者 l2 一开始就是空链表 ，那么没有任何操作需要合并，所以我们只需要返回非空链表。否则，我们要判断 l1 和 l2 哪一个链表的头节点的值更小，然后递归地决定下一个添加到结果里的结点。如果两个链表有一个为空，递归结束。”

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    if (l1 == NULL) {
        return l2;
    } else if (l2 == NULL) {
        return l1;
     } else if (l1->val < l2->val) {
        l1->next = mergeTwoLists(l1->next, l2);
        return l1;
     } else {
         l2->next = mergeTwoLists(l1, l2->next);
        return l2;
     }
}

看上去就像学霸学习，看似啥都没干，实则人家早干完了。