17. Swap Nodes in Pairs

8165 ワード
アルゴリズム#アルゴリズム# テキストリンク
道しるべ
  • 接続リストを入力、
    • をペア単位で交換する.


    1.交換値のみ（24ミリ秒）

    
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        cur = head
        
        while cur and cur.next:
            # 값만 교환
            
            cur.val, cur.next.val = cur.next.val, cur.val
            cur = cur.next.next
            
        return head

  • これは楽観的な解決方法であり、少し不規則な方法でもある.

  • 接続リストのノードを変更するのではなく、構造を変更せずに値のみを変更する方法です.

  • 接続リストは通常、様々な複雑な値の構造体から構成されるため、実際には値のみを変更することは非常に困難である.
  • しかし、この問題では、1つの値からなる単純な接続リストであり、簡単に変更することができる.

    • 2.重複構造に交換（20 ms）

    
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        root = prev = ListNode(None)
        prev.next = head
        
        while head and head.next:
            #b가 a(head)를 가리키도록 할당
            b = head.next
            head.next = b.next
            b.next = head
            
            #prev가 b를 가리키도록 할당
            prev.next = b
            
            #다음번 비교를 위해 이동
            head = head.next
            # 두 칸 이동
            prev = prev.next.next
        
        return root.next

  • 接続リストを変更すること自体が想像以上に複雑な問題です.
    なぜなら、
  • 1->2->3->5->6人接続リストがある場合、3->4を4->3に変換すると、単純な2人変換だけで終わる問題ではなく、前の2つの指の接続リストと5に接続された接続リストも一緒に変更されるからです.

  • bはaになり、aはbの次になる.

  • aの前のノードprevはbを指し,次の比較を行うためにprevは2つの格子を前方に移動する.そして次の交換を行います.

  • 接続リストのheadを指すノードは直接置換されたプールであるため、headに戻るのではなく、以前の値をそれぞれrootに設定し、rootに設定します.nextを返します.

    • 3.再帰構造に交換（20 ms）

    
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        if head and head.next:
            p = head.next
        
            #스왑된 값 리턴 받음
            head.next = self.swapPairs(p.next)
            p.next = head
            return p
        return head

  • 反復解とは異なり,ポインタの役割を果たすp変数は1つで十分であり,スタックノードを作成する必要がなくheadに直接戻ることができるため,空間的複雑さは低い.

  • pはheadnextとなり、p.nextはheadとなる.

  • その間、再帰呼び出しによって交換された値が返されます.

  • 他の接続リストの問題の解答と同様に、実際には、遡及するにつれて接続リストが続きます.
    • 登録/会員入力-#16 COSホットスポット、Proxy設定
    Json