LeetCode_21: Merge Two Sorted Lists - LeetCode

# 引言

题目链接：https://leetcode.com/problems/merge-two-sorted-lists/description/

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

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

简单归并排序 (由于这儿只有两条链表还是有序的，所以时间复杂度退化为)

时间复杂度 O(n)

空间复杂度 O(1)

c++ 版本

	class Solution
	{
	public:
	ListNode mergeTwoLists(ListNode l1, ListNode *l2)
	{
	ListNode *pRet = new ListNode(0);
	ListNode *curNode = pRet;
	while (nullptr != l1 && nullptr != l2)
	{
	if (l1->val < l2->val)
	{
	curNode->next = l1;
	l1 = l1->next;
	}
	else
	{
	curNode->next = l2;
	l2 = l2->next;
	}
	curNode = curNode->next;
	}
	if (nullptr != l1)
	{
	curNode->next = l1;
	}
	if (nullptr != l2)
	{
	curNode->next = l2;
	}
	return pRet->next;
	}
	};

go 版本

	func mergeTwoLists(l1 ListNode, l2 ListNode) *ListNode {
	pRet := &ListNode{0, nil}
	curNode := pRet
	for nil != l1 && nil != l2 {
	if l1.Val < l2.Val {
	curNode.Next = l1
	l1 = l1.Next
	} else {
	curNode.Next = l2
	l2 = l2.Next
	}
	curNode = curNode.Next
	}
	if nil != l1 {
	curNode.Next = l1
	}
	if nil != l2 {
	curNode.Next = l2
	}
	return pRet.Next
	}