Structure de données Python, liste chaînée inversée

Inverser une liste chaînée

Exemple : Étant donné une liste chaînée 1->2->3->null, la liste chaînée inversée est 3- > ;2->1->null

Une méthode plus simple consiste à utiliser la "méthode d'extraction". Cela consiste d'abord à créer un nouveau nœud vide, puis à parcourir toute la liste chaînée et à faire pointer les nœuds traversés vers le nœud principal de la liste chaînée nouvellement créée.

Par exemple, les étapes sont les suivantes :

1 Créer un nouveau nœud vide : Aucun
2->Aucun
3. .2->1->Aucun
4. 3->2->1->Aucun

Le code est très simple :

""" 
Definition of ListNode 
 
class ListNode(object): 
 
 def __init__(self, val, next=None): 
  self.val = val 
  self.next = next 
""" 
class Solution: 
 """ 
 @param head: The first node of the linked list. 
 @return: You should return the head of the reversed linked list. 
     Reverse it in-place. 
 """ 
 def reverse(self, head): 
  temp = None 
  while head: 
   cur = head.next 
   head.next = temp 
   temp = head 
   head = cur 
  return temp 
  # write your code here

Bien sûr, il existe une solution légèrement plus difficile. Nous pouvons écrire le code pour retourner sur place les nœuds dans la liste chaînée en les supprimant et en les liant séquentiellement :

""" 
Definition of ListNode 
 
class ListNode(object): 
 
 def __init__(self, val, next=None): 
  self.val = val 
  self.next = next 
""" 
class Solution: 
 """ 
 @param head: The first node of the linked list. 
 @return: You should return the head of the reversed linked list. 
     Reverse it in-place. 
 """ 
 def reverse(self, head): 
  if head is None: 
   return head 
  dummy = ListNode(-1) 
  dummy.next = head 
  pre, cur = head, head.next 
  while cur: 
   temp = cur 
   # 把摘链的地方连起来 
   pre.next = cur.next 
   cur = pre.next 
   temp.next = dummy.next 
   dummy.next = temp 
  return dummy.next 
  # write your code here

Cela devrait à noter que, lors du retrait de la chaîne, n'oubliez pas de reconnecter les zones supprimées

Merci d'avoir lu, j'espère que cela pourra aider tout le monde, merci pour votre soutien à ce site !

Pour plus d'articles sur le retournement des listes chaînées de structures de données Python, veuillez faire attention au site Web PHP chinois !