Java solution -- See explanation


  • 0
    S
     public ListNode oddEvenList(ListNode head) {
        if(head == null || head.next == null)
            return head;
        ListNode oddTrav = head;
        ListNode evenHead = head.next;
        ListNode evenTrav = evenHead;
        while(evenTrav!= null && evenTrav.next != null)
            {
                oddTrav.next = evenTrav.next;
                oddTrav = evenTrav.next;
                evenTrav.next = oddTrav.next;
                evenTrav = evenTrav.next;
                }
            oddTrav.next = evenHead;
            return head;
    }
    
    1. Store the head for odd list and even list in temp pointer and have 2 other pointers to traverse the odd and even list.

    2.Say the list is 1,2,3,4.

    In the while loop:
                 1's next (odd traverse) points to 2's next. 1 points to 3.
                  move odd traverse pointer to 3.
                 2's  next (even traverse) points to 3's next. 2 points to 4.
                 move even traverse pointer to 4.Even if it would have been null; 
    

    The while condition will handle the null conditions. The while condition ensures that odd pointer will always have an odd node to go to.

    Once the while loop breaks we know that there is no odd node and hence odd traverse next should be head of even


Log in to reply
 

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