LeetCode - Rotate List

Problem description

description

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

Analysis

The initial thought is to find the last node after rotate and make the next node become the head.

Here’s the code:

public ListNode rotateRight(ListNode head, int k) {
        if (k == 0 || head == null){
            return head;
        }
        
        ListNode dummy = new ListNode(0);
        
        dummy.next = head;
        
        ListNode first = head;
        ListNode second = head;
        
        while (k > 0){
            if (second.next != null){
                second = second.next;                
            }
            else{
                second = head;
            }
            
            k--;
        }
        
        while (second.next != null){
            first = first.next;
            second = second.next;
        }
        
        
        second.next = dummy.next;
        dummy.next = first.next;
        first.next = null;
        
        return dummy.next;
    }

However, we can know from example that k might be bigger than the size of the linked list (let it be n), so we have a O(min(k,n)) algorithm here which may be not that efficient.

we can get the size first and than make it O(n).

Here’s the code:

class Solution {
  public ListNode rotateRight(ListNode head, int k) {
    // base cases
    if (head == null) return null;
    if (head.next == null) return head;

    // close the linked list into the ring
    ListNode old_tail = head;
    int n;
    for(n = 1; old_tail.next != null; n++)
      old_tail = old_tail.next;
    old_tail.next = head;

    // find new tail : (n - k % n - 1)th node
    // and new head : (n - k % n)th node
    ListNode new_tail = head;
    for (int i = 0; i < n - k % n - 1; i++)
      new_tail = new_tail.next;
    ListNode new_head = new_tail.next;

    // break the ring
    new_tail.next = null;

    return new_head;
  }
}

What to improve

• consider the input that maybe bigger than n

• first make it become a circle and then break it.