# 引言

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

# 题目大意

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

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

# 题解

# 一句话题解

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

# 复杂度

时间复杂度 O(n)

空间复杂度 O(1)

# AC 代码

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
}
更新于 阅读次数