初级算法-链表-合并两个有序链表

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

合并两个有序链表示例.jpg

摘一个示例做个说明.
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

条件分析:

1. 两个有序链表 -> 链表是排好序的
2. 链表操作 -> 单链表只能从前往后操作

解决思路1:

1. 根据分析1、2,采用迭代方式,进行比较

先判断链表是否有空,有空链表直接返回.然后定义返回链表和当前链表及l1和l2的可变链表(因为l1、l2,不可变,不能进行链表操作).进行执行循环,第一个和第二个链表都不为空的时候执行循环操作.在循环内进行大小比较.让当前链表指向小链表.然后小节点链表指向下一个节点.当前链表指向下一个节点.当循环结束的时候,添加非空的链表到当前链表末尾.

func mergeTwoLists(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
    // 链表是否包含空,有空链表则直接返回
    if l1 == nil || l2 == nil{
        return l2 == nil ? l1 : l2
    }
    // 定义返回链表和当前链表
    var resultHead = ListNode(0),curHead = resultHead
    // 定义l1和l2的可变链表(因为l1、l2,不可变,不能进行链表操作)
    var first = l1, second = l2
    // 第一个和第二个链表都不为空的时候执行循环操作
    while first != nil && second != nil {
        // 比较大小
        if first!.val <= second!.val {
            // 当前链表的next指向小的链表
            curHead.next = first
            first = first?.next
        }else if first!.val > second!.val {
            curHead.next = second
            second = second?.next
        }
        // 当前链表指向下一个节点继续循环
        curHead = curHead.next!
    }
    // 当一个链表循环结束的时候,直接拼接另一个链表即可
    curHead.next = first == nil ? second : first
    // 返回next链表
    return resultHead.next
}

合并两个有序链表 迭代方式提交结果.jpg

解决思路2:

1. 根据分析1、2,采用递归的方式进行循环操作

先判断链表是否有空,有空链表直接返回.然后判断节点大小.让小节点的next指向合并后的链表.直到循环结束

func mergeTwoLists(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
    if l1 == nil || l2 == nil{
        return l2 == nil ? l1 : l2
    }
    if l1!.val < l2!.val {
        l1?.next = mergeTwoLists(l1?.next, l2)
        return l1
    }else{
        l2?.next = mergeTwoLists(l1, l2?.next)
        return l2
    }
}

合并两个有序链表 递归方式提交结果.jpg

测试用例:

// 正常链表
let fourNode = ListNode.init(5)
let threeNode = ListNode.init(4)
threeNode.next = fourNode
let secondNode = ListNode.init(3)
secondNode.next = threeNode
let firstNode = ListNode.init(2)
firstNode.next = secondNode
let headNode = ListNode.init(1)
headNode.next = firstNode

let fourNode1 = ListNode.init(9)
let threeNode1 = ListNode.init(6)
threeNode1.next = fourNode1
let secondNode1 = ListNode.init(5)
secondNode1.next = threeNode1
let firstNode1 = ListNode.init(2)
firstNode1.next = secondNode1
let headNode1 = ListNode.init(0)
headNode1.next = firstNode1

// 单空链表
let fourNode = ListNode.init(5)
let threeNode = ListNode.init(4)
threeNode.next = fourNode
let secondNode = ListNode.init(3)
secondNode.next = threeNode
let firstNode = ListNode.init(2)
firstNode.next = secondNode
let headNode = ListNode.init(1)
headNode.next = firstNode

考察要点:

• 递归
• 链表