Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Rotate a List k Times

Problem Statement
Given the head of a linked list, rotate the list to the right by k places.

Example 1:

Input: head = [1,2,3,4,5], k = 2
Output: [4,5,1,2,3]

Example 2:

Input: head = [0,1,2], k = 4
Output: [2,0,1]

Solution

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def length(self, head: ListNode) -> int:
        ans = 0
        while head:
            ans += 1
            head = head.next
        return ans
        
    def rotateRight(self, head: ListNode, k: int) -> ListNode:
        if k == 0:
            return head
        
        if not head:
            return head
        
        list_len = self.length(head)
        
        # Grap the m last nodes and append them in front of the list
        m = k % list_len
        if m == 0:
            return head
            
        p = head
    
        # Move the p_forward pointer by m nodes ahead
        p_forward = head
        while m > 0:
            p_forward = p_forward.next
            m -= 1
        
       
        tail = head
        new_tail = None
        while p_forward:
            tail = p_forward
            new_tail = p
            p_forward = p_forward.next
            p = p.next
         
        
        # p points to the m-th last node    
        # tails points to the last node of the list
        # new_tail points to the node just before the m-th last node
        tail.next = head
        new_tail.next = None
        
        return p