Most efficient solution I can think of (One pass)


  • 0
    M

    This solution using two pointers takes only one pass if k < length list, else 2 passes.

    public class Solution {
        public ListNode rotateRight(ListNode head, int k) {
            if(k == 0 || head == null || head.next == null) return head;
            ListNode left = head;
            ListNode right = head;
            int startingK = k;
            
            while(right != null && right.next != null) {
                if(k == 0) left = left.next;
                else k--;
                right = right.next;
            }
            if(k > 0) return rotateRight(head, (k-1) % (startingK-k+1));
            return rotate(head, left, right);
        }
        
        private ListNode rotate(ListNode head, ListNode mid, ListNode last) {
            last.next = head;
            head = mid.next;
            mid.next = null;
            return head;
        }
    }
    

Log in to reply
 

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