ホームページ  >  記事  >  バックエンド開発  >  Pythonのリンクリストの反転メソッドとは何ですか

Pythonのリンクリストの反転メソッドとは何ですか

WBOY
WBOY転載
2023-04-29 22:55:111910ブラウズ

    Python リンク リストの反転

    リンク リストを反転

    単一リンク リストのヘッド ノードを提供します。そのノードを反転してください。リンクされたリスト、そして反転されたリンクされたリストを返します。

    Pythonのリンクリストの反転メソッドとは何ですか

    • #入力: head = [1,2,3,4,5]

    • 出力: [5,4,3,2,1]

    Pythonのリンクリストの反転メソッドとは何ですか

      ##入力: head = [1,2]
    • 出力: [2,1]
    例 3:

    ##入力 : head = []
    • 出力: []
    • 解決策
    • # Definition for singly-linked list.
      # class ListNode:
      #     def __init__(self, val=0, next=None):
      #         self.val = val
      #         self.next = next
      class Solution:
          """
          解题思路:
          1.新建一个头指针
          2.遍历head链表,依次在新的头节点位置插入,达到反转的效果
          """
          def reverseList(self, head: ListNode) -> ListNode:
              # 循环
              new_head = None
      
              while head:
                  per = head.next # pre 为后置节点,及当前节点的下一个节点
      
                  head.next = new_head # 插入头节点元素
      
                  new_head = head # 把串起来的链表赋值给头指针
      
                  head = per  # 向后移一个单位
              
              return  new_head  # 返回一个新的链表
    Python反転リンクリスト関連スキル

    単一リンク リストのヘッド ノード pHead を指定すると (ヘッド ノードには値があります。たとえば、下の図では val は 1)、長さは n です。リンク リストを反転した後、そのヘッド ノードを返します。新しいリンクされたリスト。

    要件: 空間計算量 O(1)O(1)、時間計算量 O(n)O(n)。

    #入力:

    Pythonのリンクリストの反転メソッドとは何ですか#{1,2,3}

    #戻り値:

    {3,2,1}

    まず、最も基本的な逆リンク リストのコードを見てみましょう:

    # -*- coding:utf-8 -*-
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    class Solution:
        # 返回ListNode
        def ReverseList(self, pHead):
            # write code here
            cur = pHead
            pre = None
            while cur:
                nextNode = cur.next
                cur.next = pre
                pre = cur
                cur = nextNode
            return pre
    主要な式

    いくつかを見てみましょう。キーポイント:

    cur: 元のリンク リストのヘッド ノード反転の最後に、cur は pre

    の次のノードを指します。
      pre: 元のリンク リストの末尾ノードは、反転されたリンク リストの先頭ノードになります。確定申告は前です。
    • while cur: ループを反転する条件を示します。ここでは、cur が空かどうかを判断します。質問の条件に応じて他のループ条件に変更することもできます。
    • リンクリストの末尾ノードを反転します。ここでの末尾ノードは None であり、明示的な指定が記載されます後で。
    • リンク リストの反転問題では、元のリンク リストの先頭ノード、元のリンク リストの末尾ノード、逆ループ条件、および逆引きリンクリストの末尾ノード 基本的には問題ありません。
    • 次に、2 つの例を示します。

    リンク リスト内の指定された間隔を反転する

    リンク リスト内の k 個のノードごとに反転する リンク リストで指定された間隔の反転

    サイズのノード番号を持つリンク リストの m 位置と n 位置の間の間隔を反転するには、時間計算量 O(n) と空間計算量 O(1) が必要です)。

    要件: 時間計算量 O(n)、空間計算量 O(n)

    上級: 時間計算量 O(n)、空間計算量 O(1)

    入力:

    {1,2,3,4,5},2,4

    戻り値:

    {1,4,3,2,5}

    式を適用する

    この質問とベースラインの違いは、リンク リスト全体を、リンク リストの m 位置と n 位置の間の間隔の反転に適用します。式を適用しましょう:

    元のリンク リストのヘッド ノード: cur: head から開始して、 m-1 ステップを実行して cur

      元のリンク リストの末尾ノード: pre: cur
    • ## の前のノード

      #逆ループ条件 : for i in range(n,m)
    • リンクされたリストの末尾ノードを逆にします。先頭から保存してから m に移動する必要があります。 -1 ステップ、cur に到達すると、この時点で pre 位置 prePos になります。 prePos.next は、逆方向リンク リストの末尾ノードです。
    • は、前のノードと比較されます。追加の注意が必要です:
    • は、保存して head. から開始し、再度 m-1 歩進み、cur に到達したとき、このときの pre の位置が prePos になります。反転サイクルが終了したら、スレッドを再度開始します。

    リンク リスト全体が反転されないため、新しい仮想ヘッド ノード dummyNode を作成し、dummyNode.next が全体を指すようにするのが最善です。リンク リスト
    • コードの実装

    最初に数式部分のコードを見てみましょう: Pythonのリンクリストの反転メソッドとは何ですか

    # 找到pre和cur
    i = 1
    while i<m:
        pre = cur
        cur = cur.next
        i = i+1
     
    # 在指定区间内反转
    preHead = pre
    while i<=n:
        nextNode = cur.next
        cur.next = pre
        pre = cur
        cur = nextNode
        i = i+1

    コードの針と糸の部分を通す:

    nextNode = preHead.next
    preHead.next = pre
    if nextNode:
        nextNode.next = cur
    完全なコード:
    class ListNode:
        def __init__(self, x):
            self.val = x
            self.next = None
     
    class Solution:
        def reverseBetween(self , head , m , n ):
            # write code here
            dummpyNode = ListNode(-1)
            dummpyNode.next = head
            pre = dummpyNode
            cur = head
     
            i = 1
            while i<m:
                pre = cur
                cur = cur.next
                i = i+1
     
            preHead = pre
            while i<=n:
                nextNode = cur.next
                cur.next = pre
                pre = cur
                cur = nextNode
                i = i+1
            
            nextNode = preHead.next
            preHead.next = pre
            if nextNode:
                nextNode.next = cur
     
            return dummpyNode.next

    k グループごとにリンク リスト内のノードを反転する

    ノードを反転する指定されたリンク リストで k グループごとにフリップを返します。 最後のリンク リスト

    ##リンク リスト内のノードの数が k の倍数でない場合、最後に残ったノードをそのまま保持します

    ノード内の値は変更できません。変更できるのはノード自体のみです。

    空間計算量 O(1)、時間計算量 O(n)が必要です

    入力:

    {1,2, 3, 4,5},2

    戻り値:

    {2,1,4,3,5}

    式を適用する

    この質問とベースラインの違いは、リンク リスト全体の反転が k 個の反転のグループに変更されることです。ノードの数が k の倍数でない場合、残り ノードはそのまま残ります。

    まずセクションで見てみましょう。位置 1 から位置 k までのリンク リストに直面するとします:

    元のリンク リストのヘッド ノード: cur: head から開始して k -1 ステップを進み、cur

    に到達します
  • 原链表的尾节点:pre:cur前面的节点

  • 反转循环条件:for i in range(1,k)

  • 反转链表的尾节点:先定义tail=head,等反转完后tail.next就是反转链表的尾节点

  • 先看下套公式部分的代码:

    pre = None
    cur = head
    tail = head
     
     
    i = 1
    while i<=k:
        nextNode = cur.next
        cur.next = pre
        pre = cur
        cur = nextNode
        i = i+1

    这样,我们就得到了1 位置1-位置k的反转链表。

    此时:

    • pre:指向反转链表的头节点

    • cur:位置k+1的节点,下一段链表的头节点

    • tail:反转链表的尾节点

    那么,得到位置k+1-位置2k的反转链表,就可以用递归的思路,用tail.next=reverse(cur,k)

    需要注意:如果链表中的节点数不是 k 的倍数,将最后剩下的节点保持原样

    i = 1
    tmp = cur
    while i<=k:
        if tmp:
            tmp = tmp.next
        else:
            return head
        i = i+1

    代码实现

    完整代码:

    class ListNode:
        def __init__(self, x):
            self.val = x
            self.next = None
     
    class Solution:
        def reverseKGroup(self , head , k ):
           
            # write code here
            return self.reverse(head, k )
        
        def reverse(self , head , k ):
            pre = None
            cur = head
            tail = head
     
            i = 1
            tmp = cur
            while i<=k:
                if tmp:
                    tmp = tmp.next
                else:
                    return head
                i = i+1
            
            i = 1
            while i<=k:
                nextNode = cur.next
                cur.next = pre
                pre = cur
                cur = nextNode
                i = i+1
     
            tail.next = self.reverse(cur, k)
            return pre

    好了,抓住几个关键点:

    • cur:原链表的头节点,在反转结束时,cur指向pre的下一个节点

    • pre:原链表的尾节点,也就是反转后链表的头节点。最终返回的是pre。

    • while cur:表示反转循环的条件,这里是判断cur是否为空。也可以根据题目的条件改成其他循环条件

    • 反转链表的尾节点,这里的尾节点是None,后面会提到显式指定。

    以上がPythonのリンクリストの反転メソッドとは何ですかの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

    声明:
    この記事はyisu.comで複製されています。侵害がある場合は、admin@php.cn までご連絡ください。