1ms Java implementation Time O(N), Space O(1)


  • 0
    I

    The solution is easy to design , but it take some time to implement.

    use two pointers odd_current ,even_current to go through all the odd and even nodes,

    when odd_current reach its end, it will linked to the staring point of the the even which is even_head

    The following is the code in detail:

        public ListNode oddEvenList(ListNode head) {
        
        if(head == null || head.next == null){
            return head;
        }
        
        ListNode odd_head = head;
        ListNode even_head = head.next;
        
        ListNode odd_current = odd_head;
        ListNode even_current = even_head;
    
        
        
        while(odd_current != even_head || even_current != null){
            
            
            if(odd_current!=even_head && odd_current.next!=null && odd_current.next.next!=null){
                ListNode odd_next = odd_current.next.next;
                odd_current.next = odd_next;
                odd_current = odd_next;
            }else if(odd_current != even_head && (odd_current.next == null || odd_current.next.next == null)){
                odd_current.next = even_head;
                odd_current = even_head;
            }
            
            
            if(even_current!=null && even_current.next!=null && even_current.next.next !=null){
                ListNode even_next = even_current.next.next;
                even_current.next = even_next;
                even_current = even_next;
            }else if(even_current!=null && (even_current.next == null || even_current.next.next == null) ){
                even_current.next = null;
                even_current = null;
            }
            
        }
        
        
        
        
        return odd_head;
        
        
    }

Log in to reply
 

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