# Rearrange a Linked List by Separating Odd Nodes from the Even Ones

Given a linked list, rearrange it by separating odd nodes from even ones. All even nodes should come before all odd nodes in the output list and the relative order of even and odd nodes should be maintained.

For example,

Consider list {1, 2, 3, 4, 5, 6, 7}, rearranging it should yield {2, 4, 6, 1, 3, 5, 7}.

The problem can be solved either iteratively or recursively. Below is simple iterative implementation that do not use dummy node –

## C

Output:

2 -> 4 -> 6 -> 8 -> 10 -> 1 -> 3 -> 5 -> 7 -> 9 -> null

## Java

Output:

2 -> 4 -> 6 -> 8 -> 10 -> 1 -> 3 -> 5 -> 7 -> 9 -> null

### 2. Using Dummy Nodes

We can simplify above code by using two temporary dummy nodes as the start of the odd list and even list and maintaining two pointers that always points to the last node in individual lists, so appending new Nodes is easy. The dummy node gives tail something to point to initially when the result list is empty. This dummy node is efficient, since it is only temporary, and it is allocated in the stack. The loop proceeds, removing nodes from original list, and adding it to tail of even or odd list. When we are done, we rearrange the pointers so that all even nodes are followed by all odd nodes.

## C

Output:

2 -> 4 -> 6 -> 8 -> 10 -> 1 -> 3 -> 5 -> 7 -> 9 -> null

## Java

Output:

2 -> 4 -> 6 -> 8 -> 10 -> 1 -> 3 -> 5 -> 7 -> 9 -> null

### 3. Using Recursion

This is one of those nice recursive problems where the recursive solution code is much cleaner than the iterative code. You probably wouldn’t want to use the recursive version for production code however, because it will use stack space which is proportional to the length of the lists.

## C

Output:

2 -> 4 -> 6 -> 8 -> 10 -> 1 -> 3 -> 5 -> 7 -> 9 -> null

## Java

Output:

2 -> 4 -> 6 -> 8 -> 10 -> 1 -> 3 -> 5 -> 7 -> 9 -> null

Exercise: Modify the solution so that all odd nodes comes before all even nodes.

(1 votes, average: 5.00 out of 5)

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂