Algorithem_MergeTwoSortedLists#
You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.
Return the head of the merged linked list.
Example 1:
Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]
Example 2:
Input: list1 = [], list2 = []
Output: []
Example 3:
Input: list1 = [], list2 = [0]
Output: [0]
解法#
需求是合并两个有序的 LinkList，所以解法是
- 判断 list1.val 和 list2.val 的大小，
- 如果 list1.val 小于等于 list2.val，则第一个元素是 list1.val，然后递归 list1.next 和 list2—— 即比较 list1.next.val 和 list2.val 的大小
- 如果 list1.val 大于 list2.val，则第一个元素是 list2.val，然后递归 list1 和 list2.next—— 即比较 list1.val 和 list2.next.val 的大小
- 如果 list1 为空，则返回 list2，如果 list2 为空则返回 list1
代码如下：
/**
* Definition for singly-linked list.
* public class ListNode {
* public var val: Int
* public var next: ListNode?
* public init() { self.val = 0; self.next = nil; }
* public init(_ val: Int) { self.val = val; self.next = nil; }
* public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
* }
*/
class Solution {
func mergeTwoLists(_ list1: ListNode?, _ list2: ListNode?) -> ListNode? {
if list1 == nil {
return list2
}
if list2 == nil {
return list1
}
if list1!.val <= list2!.val {
list1?.next = mergeTwoLists(list1?.next, list2)
return list1
}
else {
list2?.next = mergeTwoLists(list1, list2?.next)
return list2
}
}
}