合併兩個有序鏈表的golang實現

將兩個有序鏈表合併為一個新的有序鏈表並返回。新鏈表是通過拼接給定的兩個鏈表的所有節點組成的。

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

註意：

• 兩個鏈表都是有序的
• 如果某個鏈表為空，那就直接返回另外一個有序鏈表

//如果有一條鏈是nil，直接返回另外一條鏈
if l1 == nil {
    return l2
}
if l2 == nil {
    return l1
}

然後我們就要比較兩個鏈表的節點的順序了

• 首先，我們定義一個result指針
• 比較兩個鏈表的第一個元素哪個比較小
• result指向小的那個鏈表

先來看一張圖

核心代碼：

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    //如果有一條鏈是nil，直接返回另外一條鏈
    if l1 == nil {
        return l2
    }
    if l2 == nil {
        return l1
    }
    // 定義一個結果節點
    var res *ListNode
    // 當l1節點的值大於l2節點的值，那麼res指向l2的節點，從l2開始遍歷，反之從l1開始
    if l1.Val >= l2.Val {
        res = l2
        res.Next = mergeTwoLists(l1, l2.Next)
    } else {
        res = l1
        res.Next = mergeTwoLists(l1.Next, l2)
    }
    return res
}

使用遞歸，不斷去找兩個鏈表中比較小的元素，然後result接上那個元素