61. Rotate List.md

61. Rotate List

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

Solution

• Java

  • mine

    • save the node Runtime: 164 ms, faster than 5.08%, Memory Usage: 39 MB, less than 43.10% of Java online submissions

    //O(N)time O(N)space
    public ListNode rotateRight(ListNode head, int k) {
        List<ListNode> res = new ArrayList<>();
        ListNode t = head;
        while(t != null){
            res.add(t);
            t = t.next;
            res.get(res.size() - 1).next = null;
        }
        if(res.size() < 2){
            return head;
        }
        int s = res.size();
        int index = s - k;
        while(index < 0){
            index += s;
        }
        head = new ListNode(0);
        t = head;
        for(int i = index; i < index + s; i++){
            t.next = res.get(i % s);
            t = t.next;
        }
        return head.next;
    }
    

    • Runtime: 0 ms, faster than 100.00%, Memory Usage: 38.8 MB, less than 46.55% of Java online submissions

    //O(N)time O(1)space
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null || k == 0){
            return head;
        }
        ListNode temp = new ListNode(0, head);
        ListNode count = temp;
        int size = 0;
        while(count.next != null){
            size++;
            count = count.next;
        }
        if((k = k % size) == 0){
            return head;
        }
        ListNode tail = temp;
        for(int i = size - k; i > 0; i--){
            tail = tail.next;
        }
        count.next = head;
        temp.next = tail.next;
        tail.next = null;
        return temp.next;
    }
    

  • the most votes

    Runtime: 0 ms, faster than 100.00%, Memory Usage: 39.7 MB, less than 25.86% of Java online submissions

    //O(N)time O(1)space
    public ListNode rotateRight(ListNode head, int n) {
        if (head==null||head.next==null) return head;
        ListNode dummy=new ListNode(0);
        dummy.next=head;
        ListNode fast=dummy,slow=dummy;
    
        int i;
        for (i=0;fast.next!=null;i++)//Get the total length 
            fast=fast.next;
    
        for (int j=i-n%i;j>0;j--) //Get the i-n%i th node
            slow=slow.next;
    
        fast.next=dummy.next; //Do the rotation
        dummy.next=slow.next;
        slow.next=null;
    
        return dummy.next;
    }