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;
}