Was ist die Inversionsmethode der verknüpften Python-Liste?

Umkehrung der Python-verknüpften Liste

Umgekehrt verknüpfte Liste

Geben Sie den Kopf eines Einfach verknüpfte Liste Knotenkopf, bitte kehren Sie die verknüpfte Liste um und geben Sie die umgekehrte verknüpfte Liste zurück.

• Eingabe: head = [1,2,3,4,5]

  #🎜🎜 #
• Ausgabe: [5,4,3,2,1]

• Eingabe: head = [1,2]

• Ausgabe: [2,1]
  #🎜 🎜#

Beispiel 3:

Eingabe: head = []

• #🎜🎜 #

  Ausgabe: []

• Lösung

# 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 Reverse-Linked-List-bezogene Fähigkeiten

geben Definieren Sie den Kopfknoten pHead einer einfach verknüpften Liste (der Kopfknoten hat einen Wert, in der folgenden Abbildung ist sein Wert beispielsweise 1), die Länge ist n und nach dem Umkehren der verknüpften Liste wird der Kopf der neuen Liste zurückgegeben verlinkte Liste.

Anforderungen: Raumkomplexität O(1)O(1), Zeitkomplexität O(n)O(n).

Geben Sie ein:

{1,2,3}

# 🎜🎜#Rückgabewert:

{3,2,1}

Schauen wir uns zunächst den grundlegendsten umgekehrt verknüpften Listencode an: # 🏜 , umgekehrt Am Ende der Übertragung zeigt cur auf den nächsten Knoten von pre

pre: Der Endknoten der ursprünglichen verknüpften Liste, der der Kopfknoten ist der umgekehrten verknüpften Liste. Die endgültige Rückgabe erfolgt vorab.

while cur: Stellt die Bedingung für die Umkehrung der Schleife dar. Hier wird bestimmt, ob cur leer ist. Sie können es auch entsprechend den Bedingungen der Frage in andere Schleifenbedingungen ändern Die Spezifikation wird später erwähnt.

• Um das Problem der Umkehrung der verknüpften Liste zu lösen, erfassen Sie den Kopfknoten der ursprünglichen verknüpften Liste, den Endknoten der ursprünglichen verknüpften Liste, die Umkehrschleifenbedingung usw Der Endknoten der umgekehrt verknüpften Liste ist im Grunde kein Problem.

• Geben Sie als Nächstes zwei Beispiele an:

Kehren Sie das angegebene Intervall in der verknüpften Liste um.

• Knoten in der verknüpften Liste list Alle k Gruppen umdrehen

Das angegebene Intervall in der verknüpften Liste umkehren

• Das Intervall zwischen der m-Position und der n-Position einer verknüpften Liste mit einer Knotennummer der Größe umkehren , was einen komplexen Zeitgrad O(n) und eine Raumkomplexität O(1) erfordert.

Anforderungen: Zeitkomplexität O(n), Raumkomplexität O(n)

Fortgeschritten: Zeitkomplexität O(n), Raum Komplexität O(1)Eingabe:

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

Rückgabewert:

{1,4,3,2,5}

Wenden Sie die Formel an # 🎜🎜#

Der Unterschied zwischen dieser Frage und der Grundlinie besteht darin, dass die Umkehrung der gesamten verknüpften Liste in die Umkehrung des Intervalls zwischen der m-Position und der n-Position der verknüpften Liste geändert wird Wenden Sie die Formel an. :

Der Kopfknoten der ursprünglichen verknüpften Liste: cur: Beginnen Sie mit dem Kopf und machen Sie einen weiteren m-1-Schritt, um cur

# zu erreichen. 🎜🎜#

Der Endknoten der ursprünglichen verknüpften Liste: pre: der Knoten vor cur

Umkehrschleifenbedingung: für i in range(n,m)

Kehren Sie den Endknoten der verknüpften Liste um: Sie müssen den Startpunkt vom Kopf aus speichern, dann m-1 Schritte ausführen und Wenn Sie cur erreichen, ist die Position von pre zu diesem Zeitpunkt prePos. prePos.next ist der Endknoten der umgekehrt verknüpften Liste

Im Vergleich zum vorherigen müssen Sie besonders aufpassen:

• #🎜 🎜#Sie müssen die Position prePos von pre speichern, wenn Sie am Kopf beginnen, und dann m-1 Schritte machen, um cur zu erreichen. Nachdem die Umkehrschleife beendet ist, gehen Sie den Thread erneut durch

• Da die gesamte verknüpfte Liste nicht umgekehrt wird, ist es am besten, einen neuen virtuellen Kopfknoten dummyNode und dummpyNode zu erstellen .next verweist auf die gesamte verknüpfte Liste# 🎜🎜#

• Code-Implementierung

Schauen Sie sich zunächst die folgende Formel an. Teil des Codes:

# -*- 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

Einfädeln der Nadel. Teil des Codes:

# 找到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

• Vollständiger Code:

  nextNode = preHead.next
  preHead.next = pre
  if nextNode:
      nextNode.next = cur

  # 🎜🎜#Die Knoten in der verknüpften Liste werden alle k Gruppen umgedreht.#🎜 🎜#
  Alle k Knoten in der angegebenen verknüpften Liste umgedreht und die umgedrehte verknüpfte Liste zurückgegeben in der verknüpften Liste kein Vielfaches von k ist, werden die letzten verbleibenden Knoten zurückgegeben, die unverändert bleiben
• Sie können die Werte in den Knoten nicht ändern, nur die Knoten selbst.

Erfordert Raumkomplexität O(1), Zeitkomplexität O(n)

Eingabe:

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

Rückgabewert:

{2,1,4 ,3 ,5}

Wenden Sie die Formel an

Der Unterschied zwischen dieser Frage und der Grundfrage besteht darin, dass sie auf die gesamte verlinkte Frage angewendet wird Liste Die Umkehrung wird in eine Gruppe von k Umkehrungen geändert. Wenn die Anzahl der Knoten kein Vielfaches von k ist, bleiben die verbleibenden Knoten unverändert.

Betrachten wir es zunächst in Abschnitten. Angenommen, wir stehen vor einer verknüpften Liste von Position 1 bis Position k:

Der Kopfknoten der Ursprüngliche verknüpfte Liste: cur: Beginnen Sie mit dem Kopf und machen Sie dann k-1 Schritte, um cur zu erreichen

原链表的尾节点：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，后面会提到显式指定。

Das obige ist der detaillierte Inhalt vonWas ist die Inversionsmethode der verknüpften Python-Liste?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!