21. 合并两个有序链表（简单）

• 难度: 简单
• 考察: 链表
• 来源: https://leetcode-cn.com/problems/merge-two-sorted-lists/
• 题解: https://github.com/MisterBooo/LeetCodeAnimation/blob/master/0021-Merge-Two-Sorted-Lists/Article/0021-Merge-Two-Sorted-Lists.md
• 题解: https://github.com/azl397985856/leetcode/blob/master/problems/21.MergeTwoSortedLists.md

题目

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

示例:

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

思路

常规方法

1. 两个链表其中一个为空时返回另一个链接作为结果；
2. 记录head和current头；
3. 两个链表取小值往后遍历。

递归法

1. 两个链表其中一个为空时返回另一个链接作为结果；
2. 头部较小的一个与剩下的元素合并，并返回排好序的链表头。

关键点

• 链表结构
• 边界

复杂度

• 时间复杂度：O(M+N)
• 空间复杂度：O(M+N)

代码

常规方法

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
	if l1 == nil {
		return l2
	}
	if l2 == nil {
		return l1
	}
	var head, ll *ListNode
	if l1.Val <= l2.Val {
		ll = l1
		head = ll
		l1 = l1.Next
	} else {
		ll = l2
		head = ll
		l2 = l2.Next
	}

	for l1 != nil || l2 != nil {
		if l1 == nil {
			ll.Next = l2
			ll = ll.Next
			break
		}
		if l2 == nil {
			ll.Next = l1
			ll = ll.Next
			break
		}

		if l1.Val <= l2.Val {
			ll.Next = l1
			l1 = l1.Next
		} else {
			ll.Next = l2
			l2 = l2.Next
		}
		ll = ll.Next
	}
	return head
}

递归法

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
	if l1 == nil {
		return l2
	}
	if l2 == nil {
		return l1
	}
	if l1.Val <= l2.Val {
		l1.Next = mergeTwoLists(l1.Next, l2)
		return l1
	}
	l2.Next = mergeTwoLists(l1, l2.Next)
	return l2
}