今是昨非

今是昨非

日出江花红胜火,春来江水绿如蓝

合并两个有序链表

算法_合并两个有序链表#

给定两个有序链表 list1 和 list2 的头节点。

将两个链表合并为一个有序链表。合并后的链表应该由原始的两个链表的节点拼接而成。

返回合并后的链表的头节点。

示例 1:

image1

输入: list1 = [1,2,4], list2 = [1,3,4]
输出: [1,1,2,3,4,4]

示例 2:

输入: list1 = [], list2 = []
输出: []

示例 3:

输入: list1 = [], list2 = [0]
输出: [0]

解法#

需求是合并两个有序的链表,所以解法是

  1. 判断 list1.val 和 list2.val 的大小,
  2. 如果 list1.val 小于等于 list2.val,则第一个元素是 list1.val,然后递归 list1.next 和 list2—— 即比较 list1.next.val 和 list2.val 的大小
  3. 如果 list1.val 大于 list2.val,则第一个元素是 list2.val,然后递归 list1 和 list2.next—— 即比较 list1.val 和 list2.next.val 的大小
  4. 如果 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
        }
    }
}

加载中...
此文章数据所有权由区块链加密技术和智能合约保障仅归创作者所有。