Problem:

Given a linked list, rotate the list to the right by k places, where k is non-negative.

Example 1:

Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL

Example 2:

Input: 0->1->2->NULL, k = 4
Output: 2->0->1->NULL
Explanation:
rotate 1 steps to the right: 2->0->1->NULL
rotate 2 steps to the right: 1->2->0->NULL
rotate 3 steps to the right: 0->1->2->NULL
rotate 4 steps to the right: 2->0->1->NULL

1.  Understand

Restate the problem. Come up with (additional) test cases. Identify input/output data types, potential edge cases that may result in an error. Are there any time/space constraints?

The solution will take two inputs: a linked list and a non-negative integer, k. The output will be the linked list rotated to the right k places.

It could be possible that k = 0, in which case we could just return the linked list.

What if k is greater than the length of the linked list? We can rotate by k % length of the list.

2. Match

What type of problem is this? What data structure could you use? Are there general techniques you’re familiar with that could apply?

This is a linked list problem. Since we are manipulating the nodes in the linked list, it would be beneficial to have a dummy head to maintain a pointer to the head as the node it references changes.

Since we are rotating the list by k places, we can use two pointers–one to point to the end of the list, and another to point to k % the length of the list away from the end pointer. That way we can make the node of this second pointer the new head and the end can point to the old head.

3. Plan

if head is null or head.next is null, return head
if k is 0, return head

# in case k is larger than the length
# need helper function for length
k <- k % length of linked list 

# check again if k is 0 (if len and k are same)
if k == 0, return head

# dummy head
dummy <- ListNode(0, head)
end <- head
ptr <- head

# move end k spaces away from ptr
for i in range k
  end <- end.next

# move both pointers until the end is reached
while end.next isn't null
  end <- end.next
  ptr <- ptr.next


dummy.next <- ptr.next  # new head
ptr.next <- end.next    # new tail
end.next <- head        # append rest of list

return dummy.next

4. Implement

Use your pseudocode to implement the idea in your chosen programming language

5. Review

Test your code with various input to ensure you get the intended output

I actually did this in combination with the planning phase to ensure my plan was on the right track. However, after implementing, I did notice I needed to check if k == 0 again once I changed it to k % length of the list. In this case, I had to return the head. Otherwise, I’d get the incorrect output (empty list).

6. Evaluate

What is the time/space complexity of your solution? Discuss how it could be improved if possible and if time permits.

Space Complexity: O(n)

Time Complexity: O(n)