Python-Datenstruktur umgedrehte verknüpfte Liste

Eine verknüpfte Liste umdrehen

Beispiel: Bei einer verknüpften Liste 1->2->3->null ist die umgedrehte verknüpfte Liste 3- > ;2->1->null

Eine einfachere Methode ist die Verwendung der „Extraktionsmethode“. Das heißt, zuerst einen neuen leeren Knoten zu erstellen, dann die gesamte verknüpfte Liste zu durchlaufen und die durchlaufenen Knoten auf den Kopfknoten der neu erstellten verknüpften Liste zeigen zu lassen.

Die Schritte lauten beispielsweise wie folgt:

1. Erstellen Sie einen neuen leeren Knoten: Keine
2->Keine
3 . 2->1->None
4. 3->2->1->None

Der Code ist sehr einfach:

""" 
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

Natürlich gibt es eine etwas schwierigere Lösung. Wir können den Code für das direkte Umdrehen der Knoten in der verknüpften Liste schreiben, indem wir sie nacheinander entfernen und verknüpfen:

""" 
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

Das sollte es sein Bitte beachten Sie: Vergessen Sie beim Entfernen der Kette nicht, die entfernten Bereiche wieder zu verbinden

Vielen Dank fürs Lesen, ich hoffe, es kann allen helfen, vielen Dank für Ihre Unterstützung dieser Website!

Weitere Artikel zum Umdrehen verknüpfter Listen von Python-Datenstrukturen finden Sie auf der chinesischen PHP-Website!