Rotierende verknüpfte Liste der Python-Datenstruktur

Problembeschreibung: Bei gegebener verknüpfter Liste drehen Sie die verknüpfte Liste so, dass jeder Knoten k Positionen nach rechts verschiebt, wobei k eine nicht negative Zahl ist

Beispiel: Gegebene verknüpfte Liste 1- > 2->3->4->5->null und k=2; geben 4->5->1->2->3->null zurück

Schauen wir uns zunächst den Zweck dieser Frage an. Mit anderen Worten, sie kann folgendermaßen beschrieben werden: Verschieben Sie bei einem gegebenen k-Wert den Teil der verknüpften Liste beginnend mit dem k-ten Knoten Vom letzten zum Anfang der verknüpften Liste wird der Teil 4->5 tatsächlich an den Anfang der gesamten verknüpften Liste verschoben und wird zu 4->5->1-> ;2->3->null. Es ist jedoch zu beachten, dass die Größe von k in der Frage nicht angegeben ist. Wenn k größer als die Länge der verknüpften Liste ist, müssen wir beispielsweise zuerst k verwenden, um den Rest der Länge der verknüpften Liste zu ermitteln , wenn k = 7, dann verschiebt das obige Beispiel immer noch 4->5 an den Anfang der gesamten verknüpften Liste.

Die Idee dieser Frage kann also wie folgt zusammengefasst werden:

Ermitteln Sie zunächst die Länge der gesamten verknüpften Liste
2 . Finden Sie die erforderliche Bewegung basierend auf dem k-Wert. Der Vorgänger der teilweise verknüpften Liste (3 im Beispiel)
3 Trennen Sie die verknüpfte Liste nach dem Vorgänger und verschieben Sie die zweite Hälfte Der Code lautet wie folgt:

# Definition for singly-linked list. 
# class ListNode: 
#   def __init__(self, x): 
#     self.val = x 
#     self.next = None 
 
class Solution: 
  # @param head: the list 
  # @param k: rotate to the right k places 
  # @return: the list after rotation 
  def rotateRight(self, head, k): 
    if head is None: 
      return head 
    cur = head 
    count = 1 
    # 计算链表长度 
    while cur.next: 
      cur = cur.next 
      count += 1 
    # 为节省代码量，这里是一个很有技巧的处理：用尾节点链接头结点 
    cur.next = head 
    # 此处，k为cur从尾节点到要断开部分的前驱需走的步数 
    k = count - k % count 
    # 找到前驱 
    while k != 0: 
      cur = cur.next 
      k -= 1 
    # 断开 
    head = cur.next 
    cur.next = None 
    # 因为首尾已经相连，所以直接返回前驱后面的那个节点即可，此处引用为head 
    return head 
    # write your code here

Was zu beachten ist, ist die Technik, 21 Zeilen Ende an Ende zu verbinden, was den Betrag erheblich spart Befolgen Sie in der Tat einfach die in der vorherigen Idee beschriebenen Schritt-für-Schritt-Anweisungen, und das ist kein Problem. Aber diese Technik ist wirklich großartig und es lohnt sich, sie zu erlernen. Ich habe die spezifischen Details in die Codekommentare geschrieben.

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

Weitere Artikel zur rotierenden verknüpften Liste der Python-Datenstruktur finden Sie auf der chinesischen PHP-Website!