0021.merge-two-sorted-lists

21.合并两个有序链表

题目描述

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

 

示例：

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

解题思路

代码实现

Golang 1

func mergeTwoLists1(l1 *ListNode, l2 *ListNode) *ListNode {
	if l1 == nil {
		return l2
	}
	if l2 == nil {
		return l1
	}
	ret := &ListNode{}
	if l1.Val <= l2.Val {
		ret = l1
		ret.Next = mergeTwoLists1(l1.Next, l2)
	} else {
		ret = l2
		ret.Next = mergeTwoLists1(l1, l2.Next)
	}
	return ret
}

Golang 2

func mergeTwoLists2(l1 *ListNode, l2 *ListNode) *ListNode {
	head := &ListNode{}
	ret := head
	for l1 != nil && l2 != nil {
		if l1.Val < l2.Val {
			ret.Next = l1
			l1 = l1.Next
		} else {
			ret.Next = l2
			l2 = l2.Next
		}
		ret = ret.Next
	}
	if l1 != nil {
		ret.Next = l1
	}
	if l2 != nil {
		ret.Next = l2
	}
	return head.Next
}