3ms Java solution with comments


  • 0
    J

    '''
    public class Solution {
    public void reorderList(ListNode head) {

        ListNode fast,slow,prev=head;
      
      //We will need to change the list only if its length is more than two.
        if(head==null) return;
        if(head.next==null) return;
        if(head.next.next==null) return;
        
        slow=fast=head;
        
        //Fast Runner technique to get the middle eliment.
        while(fast!=null && fast.next!=null)
        {
            prev=slow;
            slow=slow.next;
            fast=fast.next.next;
        }
        
        /*
         *fast==null if there are even number of elements.
         *move slow one step to get the first element of the second half 
        */
        if(fast!=null) {
            prev=slow;
            slow=slow.next;
        }
        
        //End the first half of the list
        prev.next=null;
        
        //Reverse the second half of the list
        ListNode revHead = revList(slow);
        ListNode next,revNext;
        
        while(revHead!=null && head!=null)
        {
            revNext=revHead.next;
            next=head.next;
            
            head.next=revHead;
            revHead.next=next;
            head=next;
            revHead=revNext;
        }
        
    }
    
    public ListNode revList(ListNode head){
        
        ListNode prev=null,cur=head,next;
        
        while(cur!=null)
        {
            next=cur.next;
            cur.next=prev;
            prev=cur;
            cur=next;
        }
        
        return prev;
    }
    

    }
    '''


Log in to reply
 

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