Leetcode 61: Rotate List Java solution

In this problem we are trying to “rotate” a list the following way:

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

Here are some examples:

Examples

At first, it might look a lot like rotating an array, which we have done in this article, but we can also notice that the rotating operation in a list is much different. Indeed, in a list we only need to do 3 operations to rotate:

1. Connect the end of the list to the head of the list
2. Disconnect the new end of the list and the new head of the list
3. Set the head to be the new head of the list

Solution

First, to find the new what the new head will be, we need to know the length of the list, since it is possible that k > n. The new head of the list will be at index:

n - nk where nk = k % n

Then, we just need to do the following:

• Obtain the reference to the new end of the list
• Remember the reference to the new head of the list and separate new end from new head with: node.next = null
• Reconnect current end and head with: lastNode.next = head
• Return the list with return newHead;