復習2

逆順接続リスト、2つのソートリストのマージ、パリティ接続リスト

03/13/2022

今日のハイライトは、接続リストを理解することです.
図に示すように、下部のものを接続リスト(Linked list)と呼ぶ.この点を理解するには、ノード、矢印、ポインタ、ヘッダ、および末尾を理解することが望ましい.
Node:グリッド自体.ノードにはnextとデータ値(value)が含まれます.
Pointer:各ノードへの次のポインタ値(?)と呼ぶ.
Head:これは最初のノードを指します.
Tail:これは最後のノードを指します.次はnoneです.
接続リストは一方向にのみ流れます.片側だけ...どうしてこんなことになったの?数え切れないほどのブログ、数え切れないほどの文章を見て、また『派斬』に戻ってきましたが、抽象的な概念と見えないデータが戻ってくるものの結合だと感じましたか?コードを回転させると、上から下へ読み込み、変数に何を格納するか、for文に入って結果値を得る方法があります.片側に流れているのが見えます.そうではないかもしれません.ここで一番重要な点は矢印方向です.逆順接続リストの問題では後述しますが、矢印の方向を変えることでシーケンスを反転するしかありません.不思議ですね.一日中理解しようと努力した.頭は知っているけど心は知らない(?)その現象も経験したことがあるが,本当にあいまいだ.

実際には、アレイリストとして保存することもできますが、なぜ矢印を書かなければならないのでしょうか.
これは南兵官トゥート様が教えてくれたものです!
熟知します!

簡単に言えば、接続リストは矢印方向の流れです.矢印はどこを指し、変数の初期化はデータの空気と流量を変更します.これが主なハイライトです.
実装された接続リスト:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, val):
        if not self.head:
            self.head = ListNode(val, None)
            return

        node = self.head
        while node.next:
            node = node.next

        node.next = ListNode(val, None)

node.next:矢印
Node:ノード自体
開始時は常にノードと矢印がない状態で開始します.次に、ノードが次のノードを指す入力が表示されると、最後に値がないまで繰り返し文に戻ります.つまり、矢印は何でもないことを示し、最後に戻ります.
これは非常に重要で、多くの応用ができるので、知らなければならない部分です.

逆順序接続リスト

アプリケーションです!
この問題は今日私の発表部分です.発表でなければ、わかりにくいです.

    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        node, prev = head, None
        while node:
            next, node.next = node.next, prev
            prev, node = node, next
        return prev
#이해하려고 팀원이 나에게 알려준 예시.
# None <- 1 2 -> 3 -> 4 -> 5 -> none
# None <- 1 <- 2 3 -> 4 -> 5 -> None
# None <- 1 <- 2 < -3 4 -> 5 -> None
# None <- 1 <- 2 <- 3 <- 4 5 -> None
# None <- 1 <- 2 <- 3 <- 4 <- 5 None   return this part.

2つのソート・リストのマージ

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
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

これは、継続的な再帰呼び出し方式です.
ここで重要なのはif文のストリームの順序です.
カッコから始まり、優先度がorより高い.不思議ですね.
そして貴liでnext、すなわち矢印でmergeTwoList関数に移動します.

パリティ接続リスト

接続リストを奇数ノードの後の偶数ノードに再編成します.空間と時間の複雑さを考えてみましょう~

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
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

最初から慣れていました:並べ替えて、各値を比較して、問題の条件を満たします.しかし、私は間違っています.
ここで,コアは偶数と奇数を最初にどのように処理するかである.odd=head(最初のノード)、偶数=head.next(最初のノードの次のノード=偶数)、偶数head=head.next(偶数ノードのヘッダ).
アルゴリズムを学ぶのは容易ではありません...後で...やるべきことが多すぎる