Java Solution with LinkedList


  • 0
    C

    My thought:

    1. Compute how many elements need to be moved to the front, which should equal k % nums.length.

    2. Use linkedlist to restore moved elements one by one, which is the 1st loop.

    3. Combine elements in array and linkedlist.
      The total running time is 294ms, complexity should be O(n).

      public class Solution {
      public void rotate(int[] nums, int k) {
      if (nums == null || nums.length == 0 || k % nums.length == 0) {
      return;
      }
      LinkedList<Integer> ll = new LinkedList<>();
      int times = 0, length = nums.length, moveToFront = k % length, tail = length - 1;
      while (times++ < moveToFront) {
      ll.add(0, nums[tail--]);
      }
      int index = 0;
      Iterator<Integer> iter = ll.iterator();
      int[] result = new int[length];
      for (int i = 0; i < length - moveToFront; i++) {
      result[i + moveToFront] = nums[i];
      }
      while (iter.hasNext()) {
      result[index++] = iter.next();
      }
      for (int i = 0; i < length; i++) {
      nums[i] = result[i];
      }
      }
      }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.