14. Merge Two Sorted Lists

3620 ワード
アルゴリズム#アルゴリズム# テキストリンク
道しるべ
  • でソートされた2つの接続リストをマージ

    • 1.再帰構造への接続

    
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if(not l1) or (l2 and l1.val > l2.val):
           #다중할당, 변수스왑
            l1, l2 = l2, l1
        
        if l1:
            l1.next = self.mergeTwoLists(l1.next, l2)
        
        return l1

  • 最初から比較して、車に戻るのは簡単です.

  • しかし,この短いコードに含まれる内容が多すぎて,理解しにくいだけでなく再帰も含まれているため,さらに困難である.

  • まずl 1,l 2の値を比較し,より小さな値を左側に出現させ,nextは再帰的に呼び出し,次の値をインターリーブする.これがこのコードのすべてである.
    △編み物が次第に一体化するにつれて.

  • if文で括弧を省略すると、同じ操作が行われます.

  • 優先度が最も高いのは比較演算(>)です.

  • 次は李さんではありません.

  • orまずandを実行します.

  • ただし、括弧で明確に表現するのが望ましい.


  • スワップ変数
    交換
  • で次の値が再帰的に呼び出され続けると、接続リストは徐々に1つに結合され、一緒に編成されます.
    最後に、L 1はNull、すなわち、コード中でl 1はNoneとなり、戻り終了後に戻り始める.
  • 実際には、このように最後に反撃を開始すると、後追跡に伴って織りなす.
  • バックグラウンドトラッキングが終了すると、2つのソートリストが1つの接続リストにマージされます.
    • <2つの接続リストをマージ>


    関連項目:参照1
    第5週のデータ分析実習課題
    BOJ 1427内部