The Problem:

In this problem, we are given a linked list and a value k, our goal is to rotate the linked list by k nodes. Basically, what is meant by that is to take k nodes from the back of the linked list and append them to the start. k can also be bigger than the size of list itself.

Before we begin trying to figure out a solution for this problem, let’s first revisit an important concepts Linked List and Recursion.

Understanding Recursion:

Recursion is essentially a function calling itself. It is frequently used to solve problems that can be divided into smaller, similar sub-problems and can be very useful in dynamic programming. To understand recursion, it can be helpful to break it down into 3 parts:

1. Base Condition: This condition prevents the recursive function from calling itself infinitely.
2. Recursive Call: This is responsible for calling the recursive function itself.
3. Small Calculation: This step, which can come before or after the Recursive Call, is responsible for performing some calculation that we need for the recursive function or for returning some result after a recursive call has been completed.

A recursive tree is a visual representation of the recursive calls made by a function. It can be very helpful in understanding how recursion works and in analyzing the time and space complexity of recursive algorithms.

Understanding Linked List:

A linked list is a linear data structure that consists of a sequence of nodes, each containing data and a reference to the next node in the list. It is often used as an alternative to arrays, as it can be more efficient in certain operations such as insertion and deletion.

To understand linked lists, it can be helpful to break it down into 3 parts:

1. Nodes: Each node in a linked list contains some data and a reference to the next node in the list.
2. Head: The head of a linked list is the first node in the list. It is used as the starting point for many operations on the list.
3. Traversal: Traversing a linked list involves starting at the head and following the references from one node to the next until the desired node is reached or the end of the list is reached.

Linked lists can be very useful in solving problems that involve dynamic data structures, as they allow for efficient insertion and deletion of elements. They can also be used in combination with other data structures, such as stacks and queues, to solve more complex problems.

Intuition & Algorithm:

With an understanding of how recursion and linked lists work, let’s try to break down the problem. We don’t have to worry about making our own linked list data structure as it is given. So, we will begin by figuring out the base condition. Which in this case would be when the recursion reaches the end of the linked list or when the next node is None.

We will also have to consider another base condition, which is when k is 0, because we would have no nodes to rotate at k = 0. Since k could be bigger than the size of the linked list it would make more sense that we divide k by size of linked list and take the remainder. We have to do this as, say k = 7 & size of list = 5 then 7%5 = 2 so we rotate 2 times.

As for replacing the nodes, we can keep track of the last and second last node as the last node will eventually become the new head and the second last will become the last node. From there it would just be breaking the link between second last and last and setting last.next to head and then making last the new head, then we simply make the recursive call with the value of k reduced by 1 until k reaches 0.

This ensures that we always have always rotated the linked list k times, given k > 0. Let's visualize the algorithm down below.

Summary of Solution

Recursively rotate a linked list to the right by k places. Keep track of the last and second last nodes, break the link between them, and set the last node as the new head. Make a recursive call with k reduced by 1 until k reaches 0. Take care of cases where k is larger than the size of the linked list by taking the remainder of k divided by the size of the list. Return the new head of the list.

Code

This can be translated to code in the following way:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if head == None or head.next == None:
            return head 
        lastNode = head 
        secondLastNode = None
        sizeofList = 1
        while lastNode.next:
            secondLastNode = lastNode
            lastNode = lastNode.next
            sizeofList += 1
        # take care of cases where k is bigger than length of list, eg when k = 7
        # and list is size 5, 7%5 = 2 so we need to rotate array by 2.
        k = k % sizeofList
        if k == 0:
            return head
        # break link from second last to last node
        secondLastNode.next = None 
        lastNode.next = head # join lastNode with the rest of the array
        head = lastNode # get rid of head
        return self.rotateRight(head, k-1)

• Time Complexity O(n*k)
• Space Complexity O(n)

The time complexity of this solution is O(n*k) This is because the function needs to traverse the linked lists at worst k times. Time taken for this operation would be proportional to the size of the linked list * k. We also have to run the recursion k times to rotate by k nodes.

Space complexity is O(n) because of recursion call stack.

This approach is simple and efficient, making it a good solution to this problem.

I hope you enjoyed this post. Stay tuned for daily LeetCode blog posts!