8 17接続リスト(交換ペアのノード)

2365 ワード
パイ アルゴリズム#アルゴリズム# テキストリンク

質問:接続リストを入力し、公平な単位で交換します.

1.値のみ交換

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


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
簡単に言えば,ノード構造は高値のみを変更する方法である.しかし、この方法は実用性が低いと言われています.接続リストは通常複雑な複数の値からなる構造体であるため、その中で値を変更するだけでは難しい(?)名前は...そうですか.

この方法は実用的ではないが,この問題では前年も短かった.

2.繰り返し構造で交換

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


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−4−5である場合、3−4を変更すると、接続された2および5も一緒に変更されるからである.これはもちろんですが、どうしてこんなに難しいのですか.かつて...;
この方法は面白そうだ.最初は、bはaを指し、aはbは次を指すように変更された.そしてaの前のノードprevはbを指し,次の比較のために2回前進する.そして質問の答えに基づいてwhileも含まれます.

3.再帰構造で交換


幽霊を使ってもっときれいなものを手に入れることができます!
# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


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を直接返すこともできるので複雑度が低い.
JWTとは?
rendering