Intuitive solution, O(n) time O(1) space


  • 0
    E

    This problem is similar to "19. Remove Nth Node From End of List", first we loop over the list to get the length of the linkedlist, just in case k is bigger than the length of the list, we take the modulo first. If after modulo k turned out to be 0, we can just go head and return the head node and skip all the following rotating steps
    Otherwise, have two pointers prev and tail, create a gap of length k between prev and tail, then keep moving until tail reaches the end of the list, now we can do the rotation by changing the connections of the pointers

    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null) {
            return head;
        }    
        int len = 0;
    // get the length of the list
        ListNode temp = head;
        while (temp != null) {
            len++;
            temp = temp.next;
        }
    // get modulo of k 
        k = k % len;
        if (k == 0) {
            return head;
        }
        ListNode prev = head;
        ListNode tail = head;
        for (int i = 0; i < k; i++) {
            tail = tail.next;
            
        }
    // create a gap of length k
        while (tail != null && tail.next != null) {
            prev = prev.next;
            tail = tail.next;
        }
    // rotation
        ListNode newHead = prev.next;
        prev.next = null;
        tail.next = head;
        return newHead;
    }

Log in to reply
 

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