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
2
3
4
5
Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL

Input: 0->1->2->NULL, k = 4
Output: 2->0->1->NULL

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
2
3
4
5
6
7
8
9
10
11
12
// 1
[1,2,3,4,5]
2
[4,5,1,2,3]
// 2
[1,2]
0
[1,2]
// 3
[1,2]
2
[1,2]

Original version (struggled with corner cases):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public ListNode rotateRight(ListNode head, int k) {
if (head == null || head.next == null) {
return head;
}
int n = getLength(head);
if (k % n == 0) {
return head;
}
k = n - k % n;
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode p = head;
ListNode prev = dummy;
while (k > 0) {
prev = p;
p = p.next;
--k;
}
prev.next = null;
dummy.next = p;
while (p.next != null) p = p.next;
p.next = head;

return dummy.next;
}

private int getLength(ListNode x) {
int count = 0;
while (x != null) {
++count;
x = x.next;
}
return count;
}

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
  • 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
      3
      for (int i = 0; i < count; ++i) { // or count - 1
      // do you job, e.g. tail = tail.next
      }
    • while:
      1
      2
      3
      4
      5
      int count = N;
      while (count > 0) { // or count - 1 > 0 or count > 1
      // do your job, e.g. tail = tail.next
      --count;
      }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public ListNode rotateRight(ListNode head, int k) {
if (head == null || head.next == null) {
return head;
}

int len = 1; // get the length and close the ring
ListNode p = head;
while (p.next != null) {
p = p.next;
++len;
} // p stops at the tail
k = k % len;
p.next = head; // close the list to make a ring

ListNode tail = head; // find the new tail
int count = len - k - 1;
// 1 2 3 4, k = 1 => count = 4 - 1 - 1 = 2
// 4 1 2 3
// tail--->tail (x2)
for (int i = 0; i < count; ++i) {
tail = tail.next;
}
ListNode newHead = tail.next;
tail.next = null;
return newHead;
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public ListNode rotateRight(ListNode head, int k) {
// Assume k is valid
if (head == null || head.next == null) {
return head;
}

int len = 1;
ListNode p = head;
while (p.next != null) {
++len;
p = p.next;
}
p.next = head; // make a ring

// k mod length
k = k % len;
if (k == 0) {
p.next = null; // <---------------- Important!
return head; // just skip it
}

// 1 2 3 4 , len = 4, k = 2
// t-->t
ListNode tail = head; // find the new tail
for (int i = 0; i < len - k - 1; ++i) { // 4 - 2 - 1 = 2 - 1 = 1 step
tail = tail.next;
}
ListNode newHead = tail.next;
tail.next = null; // cut the ring
return newHead;
}

Comment