Very simple java solution with explanation (builds on problem19)


  • 1

    This problem is easily solvable once you know Problem19. Once you go through getting a "clean" value of k (i.e. for a list of length 5 and k = 7, the "effective" value of k is 2), all you have to do is locate the node that is k hops from the tail end.

    So ultimately, you end up in a position like this:

    k = 2
    
              p1        p2  
    1 -> 2 -> 3 -> 4 -> 5 -> null
    

    Clearly at this stage you want to short-circuit p1's next Node (i.e. 4) to be the new head. At the same time p2's next value can no longer be null but instead point to the originally supplied head. Finally, update p1's new next value to null. This swapping along takes 3 lines.

        public ListNode rotateRight(ListNode head, int k) {
            if (head == null || k == 0) return head;
            int count = getCount(head);
            k = k % count; // find "effective" value of k
            if (k == 0) return head; // why do extra work if you don't need to :)
            
            // Find node k places away from tail
            ListNode slow = head;
            ListNode fast = head;
            int paces = 0;
            while (paces != k) {
            	fast = fast.next;
            	paces++;
            }
            while (fast.next != null) {
            	slow = slow.next;
            	fast = fast.next;
            }
            
            // This means fast.next is null, and need to be pointed to the old head instead
            // This means slow.next is pointing k places away and it is the new head
            fast.next = head;
            head = slow.next;
            slow.next = null;
            
            return head;
        }
        
        private int getCount(ListNode head) {
            int count = 0;
            while (head != null) {
                count++;
                head = head.next;
            }
            return count;
        }
    

  • 0
    C

    Good solution. I combined the bottom 2 while loops.

    public class Solution {
        public ListNode rotateRight(ListNode head, int k) {
            if (head == null || k == 0) return head;
            ListNode node = head;
            int n = 0;
            while (node != null){ 
                node = node.next;
                n++;
            }
            k %= n;
            ListNode slow = head, fast = head;
            while (fast.next != null) {
                fast = fast.next;
                if (k-- < 1) slow = slow.next;
            }
            fast.next = head;
            head = slow.next;
            slow.next = null;
            return head;
        }
    }

Log in to reply
 

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