题目描述

将两个有序链表合并为一个新的有序链表并返回

示例:

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

非数据结构解决方案

两个数组合并得到一个数组,利用系统自带的函数排序,把这个排序好的数组生成单向链表

let items: Array<Int> = [1,3,5,6,8,10]
let items2: Array<Int> = [0,2,4,7,7,9,11,14]

let array = items+items2
let assendArray = array.sorted(by: {$0 < $1})
let resultNode: GeneralListNode = GeneralListNode(items: assendArray)
GeneralListNode.printListNode(node: resultNode.rootNode)
// 0->1->2->3->4->5->6->7->7->8->9->10->11->14

节点定义

public class ListNode {
     public var val: Int
     public var next: ListNode?
     public init(_ val: Int) {
         self.val = val
         self.next = nil
     }
}

链表对象

// 链表对象
class GeneralListNode {

    // 根节点
    var rootNode: ListNode!
    fileprivate var items: Array<Int>
    fileprivate var index = -1
    
    init(items: Array<Int>) {
        self.items = items
        self.rootNode = createList()
    }

    fileprivate func createList() -> ListNode?{
        // 索引加一
        self.index = self.index + 1
        if index < self.items.count && index >= 0 {
            
            let item = self.items[index]
            let node =  ListNode.init(item)
            node.next = createList()  // 递归创建
            return node
        }
        return nil
    }
}

解决方案1:迭代

/// 合并两个有序(升序)的单链表
class func mergeTwoList(_ l1: ListNode?,_ l2: ListNode?) -> ListNode? {
    
    if l1 == nil {
        return l2
    }
    
    if l2 == nil {
        return l1
    }
    var newNode: ListNode?
    var newNode1 = l1
    var newNode2 = l2
    
    // 先确定newNode头结点
    if newNode1!.val < newNode2!.val {
        newNode = newNode1
        newNode1 = newNode1?.next
    } else {
        newNode = newNode2
        newNode2 = newNode2?.next
    }
    // 此处是引用,操作currentNode等于操作newNode
    var currentNode = newNode
    // 循环遍历,依次填充currentNode.next节点
    while (newNode1 != nil) && (newNode2 != nil) {
        if newNode1!.val <= newNode2!.val {
            currentNode?.next = newNode1
            newNode1 = newNode1?.next
        } else {
            currentNode?.next = newNode2
            newNode2 = newNode2?.next
        }
        currentNode = currentNode?.next
    }
    
    if newNode1 != nil && newNode2 == nil {
        currentNode?.next = newNode1
    }
    
    if newNode1 == nil && newNode2 != nil {
        currentNode?.next = newNode2
    }
    // currentNode最后指向最后一个节点
    return newNode
}

demo

测试

let items: Array<Int> = [1,3,5,6,8,10]
let listNode: GeneralListNode = GeneralListNode(items: items)

let items2: Array<Int> = [0,2,4,7,7,9,11]
let listNode2: GeneralListNode = GeneralListNode(items: items2)

let res = GeneralListNode.mergeTwoList(listNode.rootNode, listNode2.rootNode)
listNode.printListNode(node: res)

// 0->1->2->3->4->5->6->7->7->8->9->10->11

解决方案2:递归

class func recursionMethod(endNode: ListNode?,currentNode: ListNode?,_ l1: ListNode?,_ l2: ListNode?) -> ListNode? {

    var newNode1 = l1
    var newNode2 = l2
    var currentNode = currentNode
    
    if newNode1 != nil && newNode2 == nil {
        currentNode?.next = newNode1
        return endNode
    }
    
    if newNode1 == nil && newNode2 != nil {
        currentNode?.next = newNode2
        return endNode
    }
    if newNode1!.val <= newNode2!.val {
        currentNode?.next = newNode1
        newNode1 = newNode1?.next
    } else {
        currentNode?.next = newNode2
        newNode2 = newNode2?.next
    }
    currentNode = currentNode?.next
    return recursionMethod(endNode: endNode, currentNode: currentNode, newNode1, newNode2)
}

/// 合并两个有序(升序)的单链表
class func mergeTwoList2(_ l1: ListNode?,_ l2: ListNode?) -> ListNode? {
    
    if l1 == nil {
        return l2
    }
    
    if l2 == nil {
        return l1
    }
    var newNode: ListNode?
    var newNode1 = l1
    var newNode2 = l2
    
    // 先确定newNode头结点
    if newNode1!.val < newNode2!.val {
        newNode = newNode1
        newNode1 = newNode1?.next
    } else {
        newNode = newNode2
        newNode2 = newNode2?.next
    }

    let temp = recursionMethod(endNode: newNode, currentNode: newNode, newNode1, newNode2)
    return temp
}

测试

let items: Array<Int> = [1,3,5,6,8,10]
let listNode: GeneralListNode = GeneralListNode(items: items)

let items2: Array<Int> = [0,2,4,7,7,9,11,14]
let listNode2: GeneralListNode = GeneralListNode(items: items2)

let res = GeneralListNode.mergeTwoList2(listNode.rootNode, listNode2.rootNode)
listNode.printListNode(node: res)

// 0->1->2->3->4->5->6->7->7->8->9->10->11->14