Rotate List

rotateRight.py

# https://leetcode.com/problems/rotate-list/
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def rotateRight(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        length = self.length(head)
        
        if length < 2:
            return head
        
        # k = 10
        # length = 3
        # 10 / 3 = 3 remainder 1
        # --- 3*n = 9
        # --- n = 1, 2, 4
        # There is no n that gives us 10.
        # We use 3, which gets us close to 10.
        # 10 - 3*3 = 1
        
        # 23 / 5 = a / b
        # q*b + r = a
        
        # a / b => q
        # a % b => r
        
        # 0 <= r < 5
        # q*5 + r = 2
        # q = 0
        # 0*5 + r = 2
        
        # 1 -> 2 -> 3 -> 4 -> 5
        # Find n-k element in the list (5 - 2 = 3)
        # => save his successor 4, your new head
        # => kill the connection between 3 and 4 (3 points to null)
        # => traverse to the end, connect the tail to the original head
        # => and return the new head (4)
        # 1 -> 2 -> 3 -/> 4 -> 5
        
        # When doing modulus, you're always getting the remainder (r)
        # When doign division, you're always getting the quotient (q, how many)
        k %= length
        
        if not head or not head.next:
            return head
        
        currentNode = head
        # k = 1, length = 5
        
        # n + 1 = k
        # 1 
        for i in range(length - k - 1):
            currentNode = currentNode.next
            
        newTail = currentNode
        while currentNode.next:
            currentNode = currentNode.next
        lastNode = currentNode
        lastNode.next = head
        
        successor = newTail.next
        newTail.next = None
        
        return successor
        
        
    def length(self, head):
        currentNode = head
        count = 0
        while currentNode:
            count += 1
            currentNode = currentNode.next
        return count