更多精彩內(nèi)容，請關(guān)注【力扣簡單題】。

題目

難度：★★☆☆☆
類型：鏈表

將兩個有序鏈表合并為一個新的有序鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節(jié)點(diǎn)組成的。

示例

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

解答

融合兩個有序鏈表，首先定義一個臨時結(jié)點(diǎn)pre_head，其后連接融合結(jié)果。然后遍歷兩個鏈表，獲得當(dāng)前的結(jié)點(diǎn)l1和l2，結(jié)果鏈表后連接這兩個結(jié)點(diǎn)中較小的結(jié)點(diǎn)，并把該結(jié)點(diǎn)后移一位重新比較，直到其中一個鏈表已經(jīng)遍歷結(jié)束，再把另一個鏈表的剩余部分掛在到當(dāng)前結(jié)果上，返回臨時結(jié)點(diǎn)pre_head后掛的結(jié)果鏈表即可。

class Solution:
    def mergeTwoLists(self, l1, l2):
        # 處理特殊情況
        if not l1:
            return l2
        if not l2:
            return l1

        pre_head = ListNode(0)          # 定義一個臨時結(jié)點(diǎn)，用于掛載結(jié)果
        cur = pre_head                  # 定義當(dāng)前結(jié)點(diǎn)

        while l1 and l2:                # 如果兩個鏈表當(dāng)前位置均不為空
            if l1.val > l2.val:         # 判斷兩個結(jié)點(diǎn)的大小
                cur.next = l2           # 將數(shù)值較小的結(jié)點(diǎn)掛載當(dāng)前結(jié)點(diǎn)后面
                l2 = l2.next            # 數(shù)值較小的結(jié)點(diǎn)后移
            else:
                cur.next = l1
                l1 = l1.next

            cur = cur.next              # 后移當(dāng)前結(jié)點(diǎn)

        if l1:
            cur.next = l1               # 把鏈表剩下的部分掛在當(dāng)前結(jié)點(diǎn)
        if l2:
            cur.next = l2
        return pre_head.next            # 返回融合后的鏈表

如有疑問或建議，歡迎評論區(qū)留言~