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

Python リンク リストの反転

リンク リストを反転

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

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

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

##入力: 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)。

#入力:

#{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 が全体を指すようにするのが最善です。リンク リスト

• コードの実装

最初に数式部分のコードを見てみましょう:

# 找到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 サイトの他の関連記事を参照してください。