Is My Code in one-pass and in-place? [Accepted and in Java]


  • 0
    E

    My approach is like the following. I use an array to store the sequence values from m to n of the list. then i reassign the value of these nodes with reversed values. the code is in the following. and I was confused whether my approach is in one-pass? and is there other approach that is in-place and in one-pass?

    if(head == null || m == n)
    		 return head;
    	 int [] seq = new int[n-m+1];
    	 ListNode start = head;
    	 ListNode temp = head;
    	 int i = 1;
    	 while(i<m){
    		 start = start.next;
    		 i++;
    	 }
    	 temp = start;
    	 seq[0] = temp.val;
    	 int j=1;
    	 while(i<n){
    		 temp = temp.next;i++;
    		 seq[j++] = temp.val;
    	 }
    	 
    	 for(j = n-m;j>=0;j--){
    		 start.val = seq[j];
    		 start = start.next;
    	 }
    	 return head;

  • 0
    W

    I think it's more like two-pass...but I don't how to get one-pass either,
    good idea appreciated...


  • 8
    P

    I got one-pass and in-place solution in Java:

        if(head==null || head.next==null) return head;
        
        ListNode newhead = new ListNode(0);
        newhead.next = head;
        ListNode p = newhead;
        int k = 1;
        
        while(k++<m) p = p.next;
        
        ListNode p1 = p.next;
        ListNode temp = p1;
        
        while(m++<n) {
            temp = p1.next;
            p1.next = temp.next;
            temp.next = p.next;
            p.next = temp;
        }
        
        return newhead.next;

  • 0
    E

    Your approach is not in place, because you use another O(n) storage, ie., the seq array.


Log in to reply
 

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