Python data structure rotating linked list

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

Example: Given linked list 1-> 2->3->4->5->null and k=2; return 4->5->1->2->3->null

First of all, let’s look at the purpose of this question. In fact, in other words, it can be described like this: given a k value, move the part of the linked list starting from the k-th node from the last to the front of the linked list. As far as the example is concerned, the 4->5 part is actually moved to the front of the entire linked list and becomes 4->5->1->2->3->null. However, it should be noted that the size of k is not given in the question. When k is larger than the length of the linked list, we need to first use k to find the remainder of the length of the linked list. For example, if k = 7, then the above The example still moves 4->5 to the front of the entire linked list.

So, the idea of ​​​​this question can be summarized like this:

1. First find the length of the entire linked list
2. Find the need to move based on the k value The predecessor of the partial linked list (3 in the example)
3. Disconnect the linked list after the predecessor and move the second 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 
    # 计算链表长度 
    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

What needs to be noted is the technique of connecting 21 lines end to end, which greatly saves the amount of our code. In fact, it is no problem to just follow the step by step described in the previous ideas. . But this technique is really great and worth learning. I wrote the specific details in the code comments.

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

For more articles related to the rotating linked list of Python data structure, please pay attention to the PHP Chinese website!