# 61. Rotate List

Reference: LeetCode

Difficulty: Medium

## Problem

Given a linked list, rotate the list to the right by $k$ places, where $k$ is non-negative ($k \geq 0$).

**Note:**

**Example:**

1 | Input: 1->2->3->4->5->NULL, k = 2 |

## Analysis

**Methods:**

- Calculate the
`length`

. - Connect the last node to the head. Make a
`ring`

. - Find the new
`tail`

, and return its next as a new head and set it`null`

before returning. **Time:**$O(N)$**Space:**$O(1)$

## Code

**Test Case:**

1 | // 1 |

Original version (struggled with corner cases):

1 | public ListNode rotateRight(ListNode head, int k) { |

**Improvement:**

**Note:**

`k`

could be greater than the length of the list. Do`k % len`

.- I can add
`if`

statement to return immediately if`k`

equals`0`

or`len`

.- But notice that you might have created the ring and you must
`set it null`

! Otherwise, it will return a ring causing infinitely looping.`Memory Limit Exceeded`

- But notice that you might have created the ring and you must
`Draw a graph`

for a simple case to see how many steps to go.**Don’t just think!**- Counting templates:
- for:
**Use this one!**1

2

3for (int i = 0; i < count; ++i) { // or count - 1

// do you job, e.g. tail = tail.next

} - while:
1

2

3

4

5int count = N;

while (count > 0) { // or count - 1 > 0 or count > 1

// do your job, e.g. tail = tail.next

--count;

}

- for:

1 | public ListNode rotateRight(ListNode head, int k) { |

Here is the code I wrote in the second time. Forgot to restore the ring (I removed the bug already). `Memory Limit Exceeded`

1 | public ListNode rotateRight(ListNode head, int k) { |

Comment