Quelle est la méthode d'inversion de la liste chaînée Python

Inversion de la liste chaînée python

Liste chaînée inversée

Vous donner la tête d'un Liste chaînée unique Tête de nœud, veuillez inverser la liste chaînée et renvoyer la liste chaînée inversée.

• Entrée : head = [1,2,3,4,5]

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

• Entrée : head = [1,2]

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

Exemple 3 :

Entrée : head = []

• #🎜🎜 #

  Sortie : []

• Solution

# 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 compétences liées

give Définissez le nœud principal pHead d'une liste chaînée unique (le nœud principal a une valeur, par exemple, dans la figure ci-dessous, sa valeur est 1), la longueur est n, et après avoir inversé la liste chaînée, renvoyez la tête du nouveau liste chaînée.

Exigences : complexité spatiale O(1)O(1), complexité temporelle O(n)O(n).

Entrez :

{1,2,3}

# 🎜🎜#Valeur de retour :

{3,2,1}

Examinons d'abord le code de liste chaînée inversée le plus basique : # 🎜 🎜#

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

Formule clé

Saisissez quelques points clés :

cur : Le nœud principal de la liste chaînée d'origine , à l'envers A la fin du transfert, cur pointe vers le nœud suivant de pre

• pre : le nœud de queue de la liste chaînée d'origine, qui est le nœud de tête de la liste chaînée inversée. Le retour final est pré.

• while cur : Représente la condition d'inversion de la boucle, ici pour déterminer si cur est vide. Vous pouvez également le changer en d'autres conditions de boucle en fonction des conditions de la question

• Inversez le nœud de queue de la liste chaînée. Le nœud de queue ici est Aucun et explicite. la spécification sera mentionnée plus tard.

• Pour le problème de l'inversion de la liste chaînée, saisissez le nœud principal de la liste chaînée d'origine, le nœud de queue de la liste chaînée d'origine, la condition de boucle inversée et le nœud de queue de la liste chaînée inversée Un personnage principal, fondamentalement pas de problème.

Ensuite, donnez deux exemples :

Inversez l'intervalle spécifié dans la liste chaînée

Nœuds dans la liste chaînée list Retournez tous les k groupes

Inversez l'intervalle spécifié dans la liste chaînée

Inversez l'intervalle entre la position m et la position n d'une liste chaînée avec un numéro de nœud de taille , ce qui nécessite un degré de temps complexe O(n), une complexité spatiale O(1).

Exigences : complexité temporelle O(n), complexité spatiale O(n)

Avancé : complexité temporelle O(n) ), espace complexité O(1)

Entrée :

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

Valeur de retour :

{1,4,3,2,5}

Appliquer la formule # 🎜🎜#

La différence entre cette question et la ligne de base est que l'inversion de toute la liste chaînée est remplacée par l'inversion de l'intervalle entre la position m et la position n de la liste chaînée. appliquez la formule. :

Le nœud principal de la liste chaînée d'origine : cur : En partant de head, faites un autre pas m-1 pour atteindre cur

# 🎜🎜#

Le nœud de queue de la liste chaînée d'origine : pre : le nœud devant cur

• Condition de boucle inverse : pour i in range(n,m)

• Inversez le nœud de queue de la liste chaînée : vous devez enregistrer le point de départ de head, puis faire m-1 pas, et lorsque vous atteignez cur, la position de pre à ce moment est prePos. prePos.next est le nœud de queue de la liste chaînée inversée

• Par rapport au précédent, vous devez prêter une attention particulière :
• .

  #🎜 🎜#Vous devez enregistrer la position prePos de pre lorsque vous partez de la tête puis faire des pas de m-1 pour atteindre cur. Une fois la boucle d'inversion terminée, parcourez à nouveau le fil

Étant donné que toute la liste chaînée n'est pas inversée, il est préférable de créer un nouveau nœud principal virtuel dummyNode et dummpyNode .next pointe vers l'intégralité de la liste chaînée# 🎜🎜#

• Implémentation du code

Regardez d'abord la formule suivante Une partie du code :

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

Enfiler l'aiguille Une partie du code :

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

Code complet :

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

# 🎜🎜#Les nœuds de la liste chaînée sont inversés tous les k groupes#🎜 🎜#Inversez tous les k nœuds dans la liste chaînée donnée et renvoie la liste chaînée inversée

Si le nombre de nœuds dans la liste chaînée n'est pas un multiple de k, renvoie les derniers nœuds restants restent tels quels

Vous ne pouvez pas modifier les valeurs dans les nœuds, uniquement les nœuds eux-mêmes.

Nécessite une complexité spatiale O(1), une complexité temporelle O(n)

Entrée :

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

Valeur de retour :

{2,1,4 ,3 ,5}

Appliquer la formule

La différence entre cette question et la ligne de base est qu'elle s'appliquera à l'ensemble de la question liée list L'inversion est transformée en un groupe de k inversions. Si le nombre de nœuds n'est pas un multiple de k, les nœuds restants restent tels quels.

Regardons-le d'abord par sections. Supposons que nous soyons confrontés à une liste chaînée de la position 1 à la position k :

Le nœud principal du liste chaînée originale : cur : de Commencez par la tête, puis faites des pas k-1 pour atteindre 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，后面会提到显式指定。

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!