Java 1ms Solution without iterating the whole list first


  • 1
    M

    We don't always need to loop through the whole list in the first place.
    I believe most of us are using the two pointers. So if k is greater than the list's length, the fast pointer will iterate to the end of the list while iterating from 1 to k. And at this point we know the length of the list, which equals i (current iteration times). Then we could set i to 0 and k to k%i and iterate again. For long list and a small 'k', this code would work a bit faster.

    Codes:

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

  • 0
    N

    But aren't you iterating through the whole list when you do
    for(int i=1;i<=k;i++){
    fast = fast.next;
    if(fast == null){fast=head;k=k%i;i=0;}
    }
    while(fast.next!=null){
    fast = fast.next;
    slow = slow.next;
    }

    So at least one iteration is required right?


  • 2
    M

    @neha25
    You're absolutely right. I think we always need to iterate the list at least once. But most solutions I saw here iterate the whole list first to get the length of the list which I think is unnecessary. That's why I think my solution will be a bit faster for a long list with a small 'k'.

    Thanks!


Log in to reply
 

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