Odd Even Linked List

Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.

You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.

Example:
 Given 1->2->3->4->5->NULL,
 return 1->3->5->2->4->NULL.
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head == null) 
            return null; 
        if (head.next == null)
            return head; 
        ListNode cur = head;
        //keep track of the index so we know whether it is odd or even 
        int count = 0; 
        //4 important nodes
        ListNode evenHead = new ListNode (0);
        ListNode oddHead = new ListNode (0); 
        ListNode evenCur = new ListNode (0);
        ListNode oddCur = new ListNode (0); 
        while (cur.next != null) {
            count++;
            ListNode afterCur = cur.next; 
            //if this is an even node
            if (count % 2 == 0) {
                if (count == 2) {
                    //set the second node as evenHead 
                    evenHead = cur; 
                }
                //Simply update evenCur 
                evenCur = cur; 
            } else if (count % 2 == 1) {
                // if this is an odd node 
                if (count == 1) {
                    //set the first node as oddHead 
                    oddHead = cur; 
                } else {
                    //add next node to oddCur 
                    oddCur.next = cur;
                    //add next node to evenCur 
                    evenCur.next = afterCur; 
                    //joint odd-list and even-list again after modification  
                    cur.next = evenHead; 
                }
                //update oddCur 
                oddCur = cur;
            }
            //update cur
            cur = afterCur;
        }
        
        //Need to deal with the tail, since it is not accessed in the loop
        count++;      
        if (count % 2 == 0) {
            return oddHead; 
        } else {
            oddCur.next = cur; 
            cur.next = evenHead; 
            evenCur.next = null;
            return oddHead; 
        }
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s