A rotated linked list of Python data structures

Given a linked list, rotate the list so that each node moves k to the right, where k is a non-negative number

Example: give the linked list 1- > 2- > 3- > 4- > 5- > null and k = 2; Return to the 4 - > 5- > 1- > 2- > 3- > null

First of all, observe 1 to achieve the purpose of this problem, in fact, to put it another way, can be described as follows: given a value of k, the linked list from the penultimate k node after the part moved to the front of the list, in the case of the sample, actually 4- > So this part of 5 moves to the front of the whole list, and it becomes 4 minus > 5- > 1- > 2- > 3- > null. However, it is important to note that the size of k is not given in the question. When k is larger than the length of the list, we need to use k to find the length of the list first. For example, if k = 7, then the above example will still be 4- > 5 move to the front of the entire list.

So, the idea of this problem can be summarized as follows:

1. Figure out the length of the entire list
2. Find the precursor of the partial list that needs to be moved according to the k value (3 in the sample)
3. Disconnect the list after the precursor and move the back half

The code is as follows:

# 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 
    #  Calculate the list length  
    while cur.next: 
      cur = cur.next 
      count += 1 
    #  To save code, here is 1 Here's a tricky trick: link the header with the tail  
    cur.next = head 
    #  Here, k for cur The number of steps taken from the tail node to the precursor to be disconnected  
    k = count - k % count 
    #  Find precursor  
    while k != 0: 
      cur = cur.next 
      k -= 1 
    #  Disconnect the  
    head = cur.next 
    cur.next = None 
    #  Since heads and tails are already joined, you can simply return to the node behind the precursor, as referenced here head 
    return head 
    # write your code here 

Note that the 21 lines end to end technique saves us a lot of code, even if we follow the 1 step described in the previous thought. But it's a great technique to learn. I wrote the details in the code comments.

Thank you for reading, I hope to help you, thank you for your support of this site!