C----合并两个有序链表

将两个有序链表合并为一个新的有序链表并返回。

新链表是通过拼接给定的两个链表的所有节点组成的。
           

示例：

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

递归实现：

先比较节点的两个val大小，把一个小val所在节点的指针指向下一层小val返回的节点，必须设置返回的判断条件；递归调用一个函数，最后将返回一个完整的有序链表

/* Definition for singly-linked list.
   struct ListNode {
       int val;
       ListNode *next;
       ListNode(int x) : val(x), next(NULL) {}
   }; */
class Solution
{
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2)  //递归实现，尽量不用
    {
        if (l1 == nullptr)
            return l2;
        if (l2 == nullptr)
            return l1;
        if (l1->val < l2->val)
        {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        }
        else
        {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
};
           

/* Definition for singly-linked list.
	struct ListNode {
	   int val;
	   struct ListNode *next;
   }; */
Node* mergeTwoLists(Node* List1, Node* List2) {
	if (List1 == NULL && List2 == NULL)
		return NULL;
	if (List1 == NULL)
		return List2;
	if (List2 == NULL)
		return List1;
	Node *ptr, *result1;
	Node *result2 = (List1->val <= List2->val) ? List1 : List2; 
	result1 = result2;
	while (List1&&List2) {
		if (List1 && List1->val <= List2->val) {
			ptr = List1;
			List1 = List1->next;
		}
		else if (List2 && List2->val <= List1->val) {
			ptr = List2;
			List2 = List2->next;
		}
		if (result2 != List1 && result2 != List2) {
			result1->next = ptr;
			result1 = result1->next;
		}
	}
	result1->next = List1 ? List1 : List2;
	return result2;
}