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 hereVielen Dank fürs Lesen, ich hoffe, es kann Ihnen helfen, vielen Dank für Ihre Unterstützung dieser Website!
