Monday, May 1, 2017

Leetcode - 61. Rotate List(linkedlist)

61. Rotate List
medium
https://leetcode.com/problems/rotate-list/#/submissions/1
Given a list, rotate the list to the right by k places, where k is non-negative.
For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.

思路: - find out how many times to rotate: k%len
           - each time, do rotate operation by moving last node in list to the new head
           - edge case: len = 1

Complexity: Time O(k%len*N) ~ O(N) Space O(1)

public class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if(head == null || head.next == null)return head;
        //find size
        int len = 0;
        ListNode cur = head;
        while(cur != null){
            len++;
            cur = cur.next;
        }
        int times = k % len;//len 5 6times, actually rotate once!
        ListNode nHead = head;
        for(int i = 0; i < times; i++){
            nHead = doRotation(nHead);
        }
        return nHead;
    }
    
    public ListNode doRotation(ListNode head){
        ListNode cur = head;
        while(cur.next != null && cur.next.next != null){
            cur = cur.next;
        }
        ListNode nHead = cur.next;
        cur.next = cur.next.next;
        nHead.next = head;
        return nHead;
    }
}

No comments:

Post a Comment