requirements

Give you the head of a linked list, rotate the list, and move each node k positions to the right.

Example 1:

Input: head = [1,2,3,4,5], k = 2 output: [4,5,1,2,3]Copy the code

Example 2:

Input: head = [0,1,2], k = 4Copy the code

Tip:

  • The number of nodes in the linked list is in the range [0, 500]
  • -100 <= Node.val <= 100
  • 0 <= k <= 2 * 109

The core code

class ListNode:
    def __init__(self, val=0.next=None) :
        self.val = val
        self.next = next
        
class Solution:
    def rotateRight(self, head: ListNode, k: int) -> ListNode:
        if head == None or head.next= =None:
            return head
        prob = head
        counter = 1
        while prob.next! =None:
            counter += 1
            prob = prob.next
        prob.next = head
        prob_new = head
        if k >= counter:
            k = k % counter
        for i in range(counter - k - 1):
            prob_new = prob_new.next
        new_head = prob_new.next
        prob_new.next = None
        return new_head
Copy the code

Another solution

class ListNode:
    def __init__(self, val=0.next=None) :
        self.val = val
        self.next = next
        
class Solution:
    def rotateRight(self, head: ListNode, k: int) -> ListNode:
        if head == None:
            return head
        h = ListNode(-1)
        h.next = head
        prob = h
        prob1 = h
        counter = 0
        while prob.next! =None:
            counter += 1
            prob = prob.next
        
        if k > counter:
            k = k % counter
        
        for i in range(counter - k):
            prob1 = prob1.next
        
        temp = prob1.next
        prob1.next = None

        prob2 = temp
        hh = ListNode(-1)
        hh.next = temp
        prob2 = hh
        while prob2.next! =None:
            prob2 = prob2.next
        prob2.next = h.next
        return hh.next
Copy the code

In the first solution, we turn our linked list into a circle, and then we count which node we want to break at. Second solution: we directly find the node to disconnect, save the subsequent nodes, then disconnect the node followed by None, after traversing to the end of the save node, then attach our head node to our node to complete the rotation.