18. Odd Even Linked List

4984 ワード
アルゴリズム#アルゴリズム# テキストリンク
道しるべ

  • 接続リストを奇数ノードの後の偶数ノードに再編成します.

  • 空間複雑度O(1),時間複雑度O(n)


    • 1.重複構造を使用したパリティノードの処理

    
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def oddEvenList(self, head: ListNode) -> ListNode:
        #예외 처리
        if head is None:
            return None
        
        odd = head
        even = head.next
        even_head = head.next
        
        #반복하면서 홀짝 노드 처리
        while even and even.next:
            odd.next, even.next = odd.next.next, even.next.next
            odd, even = odd.next, even.next
            
        #홀수노드의 마지막을 짝수 헤드로 연결
        odd.next = even_head
        return head

  • コンストレイントがない場合は、接続リストをリストに変換し、Pythonリストで提供される各種関数(ホイールなど)を使用すると、より簡単に、より直感的に、より迅速に解くことができます.

  • Python内蔵関数の実行速度がずっと速いからです.

  • But、この問題の解き方は優雅ではありません.

  • 単一ノード(奇数)、偶数ノード(偶数)を構成し、奇数ノードの最後のノードを偶数ノードの最初のノードに接続します.

  • 入力値は次のように考えられます.

  • 奇数変数はhead、偶数変数はheadです.次です.
  • 偶数の頭はheadです.nextなので偶数head=偶数=headです.まずは次から

  • whileサイクルで処理します.

  • 最初の繰り返しでは、奇数oddは1−>3で接続され、3は値である.
    偶数の偶数は2->4で、値は4です.

  • 2つ目は3->5と4->Noneで、最後に5とNoneが残っています.


  • 複数の割当てodd.next, odd = odd.next.next, odd.next

  • 残念ながらあり得ません.

  • 最初の繰返しでは1−>3であったがoddは2であった.現在、oddはheadと同じ参照であり、headです.次は2ですから.

  • 所望の結果は1−>3,奇数は3であり,このように複数の割当てに処理すると異なる結果が生じる.

  • ただし、パリティ処理を1つにマージし、次のように2つの行に分けることができます.
    • odd.next, even.next = odd.next.next, even.next.next
 odd, even = odd.next, even.next
    このように処理すると,奇数奇数は5,偶数奇数はNoneとなる.

  • 今は奇数nextを偶数headver headに接続します.

  • そして頭を打ち返す

  • headは1,even headは2であるため,前処理の内容により1から結果をリストすると1−>3−>5−>2−>4−>Noneとなる.

  • odd,偶数,偶数headなどの変数の使用はnの大きさとは無関係であるため,空間複雑度もO(1)で制約条件を満たす.
    • Observer Pattern
    QDIalog,QFileDialogおよびQdesktopServicesの使用方法