Liste chaînée tournante de la structure de données Python

Description du problème : étant donné une liste chaînée, faites pivoter la liste chaînée de sorte que chaque nœud se déplace de k positions vers la droite, où k est un nombre non négatif

Exemple : Étant donné la liste chaînée 1- > 2->3->4->5->null et k=2; renvoie 4->5->1->2->3->null

Tout d'abord, regardons le but de cette question. En fait, en d'autres termes, elle peut être décrite ainsi : étant donné une valeur k, déplacez la partie de la liste chaînée à partir du k-ème nœud. du dernier vers le début de la liste chaînée En ce qui concerne l'exemple, la partie 4->5 est en fait déplacée vers l'avant de toute la liste chaînée et devient 4->5->1->. ;2->3->nul. Cependant, il convient de noter que la taille de k n'est pas donnée dans la question. Lorsque k est supérieur à la longueur de la liste chaînée, nous devons d'abord utiliser k pour trouver le reste de la longueur de la liste chaînée. , si k = 7, alors ce qui précède. L'exemple déplace toujours 4->5 au début de toute la liste chaînée.

Donc, l'idée de​​cette question peut être résumée ainsi :

1 Trouvez d'abord la longueur de la liste chaînée entière
2. . Trouvez le mouvement requis en fonction de la valeur k Le prédécesseur de la liste chaînée partielle (3 dans l'exemple)
3. Déconnectez la liste chaînée après le prédécesseur et déplacez la seconde moitié

Le. le code est le suivant :

# 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

Ce qu'il faut noter, c'est la technique de connexion de 21 lignes bout à bout, ce qui permet d'économiser beaucoup d'argent de notre code. En fait, suivez simplement le pas à pas décrit dans l'idée précédente, et pas de problème. Mais cette technique est vraiment géniale et mérite d’être apprise. J'ai écrit les détails spécifiques dans les commentaires du code.

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

Pour plus d'articles liés à la liste chaînée rotative de la structure de données Python, veuillez faire attention au site Web PHP chinois !