# Segregate even and odd nodes in LinkedList

Problem Statement : Segregate even and odd nodes in LinkedList

Given a LinkedList of integers. Modify the LinkedList in such a way that in Modified LinkedList all the even numbers appear before all the odd numbers in LinkedList.

Also, note that the order of even and odd numbers should remain the same.

Examples:

```Example 1:
Input: 1→2→3→4→5→6→Null
Output: 2→4→6→1→3→5→Null
Explanation :
Odd Nodes in LinkedList are 1,3,5 and
Even Nodes in LinkedList are 2,4,6
In Modified LinkedList all even Nodes comes before
all Odd Nodes. So Modified LinkedList looks like
2→4→6→1→3→5→Null. Order of even and odd Nodes is

Example 2:
Input: 1→3→5→Null
Output: 1→3→5→Null
Explantion: As there are no Even Nodes in LinkedList,

Example 3:
Input: 2→4→6→8→Null
Output: 2→4→6→8→Null
Explanation: As there are no Odd Nodes in LinkedList,

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

### Intuition :

The Intuition is to Split the LinkedList into two parts. One Contains all the Even Nodes and the other contains all the Odd Ends. After obtaining two LinkedLists we attach odd LinkedList at the end of the Even LinkedList.

To split the LinkedList take two dummy Nodes which act as the Heads of the odd and Even LinkedList. Traverse the original LinkedList. While traversing if the Node is odd remove the Node from the original LinkedList and add to odd LinkedList. Similarly for the Even Node too.

After Traversing we obtain two LinkedList with all odd and all Even Nodes. Attach odd LinkedList at the end of Even LinkedList. As we are appending nodes to Odd and Even LinkedLists one by one the order of Nodes is undisturbed.

### Algorithm Visual Representation :  As 1 is odd Node, Removing 1 from LinkedList and appending to OddLinkedList As 2 is Even Node, Removing 2 from LinkedList and appending to EvenLinkedList As 3 is odd Node, Removing 3 from LinkedList and appending to OddLinkedList As 4 is Even Node, Removing 4 from LinkedList and appending to Even LinkedList   Code:

## C++ Code

``````#include <bits/stdc++.h>
using namespace std;

class ListNode
{
public:
int val;
ListNode *next;
ListNode(int x)
{
val = x;
next = nullptr;
}
};

{
for (; curr != nullptr; curr = curr->next)
cout << curr->val << "-->";
cout << "null" << endl;
}

void InsertatLast(int value) // Function for creating a LinkedList
{

ListNode *newnode = new ListNode(value);
head = newnode, tail = newnode;
else
tail = tail->next = newnode;
}

ListNode *SegregatetoOddEVen()
{
while (curr)
{
// Breaking the Link of the curr Node.
temp = curr;
curr = curr->next;
temp->next = nullptr;

if (temp->val & 1) // If odd Node,append to odd LinkedList
{
oddTail->next = temp;
oddTail = temp;
}
else // If Even Node,append to even LinkedList
{
evenTail->next = temp;
evenTail = temp;
}
}
}

int main()
{
InsertatLast(1);
InsertatLast(2);
InsertatLast(3);
InsertatLast(4);
cout << "Initial LinkedList : " << endl;
cout << "LinkedList After Segregration " << endl;
return 0;
}
``````

Output :

1→2→3→4→null

2→4→1→3→null

Time Complexity: O(N) N is the number of Nodes in LinkedList. As we are traversing LinkedList once.

Space Complexity: O(1) We are just Manipulating the Links, not using any extra space.

## Java Code

``````import java.util.*;

class ListNode
{
int val;
ListNode next;
ListNode(int x)
{
val = x;
next = null;
}
}

class TUF{

{
for (; curr != null; curr = curr.next)
System.out.print(curr.val+"-->");
System.out.println("null");
}

static void InsertatLast(int value) // Function for creating a LinkedList
{

ListNode newnode = new ListNode(value);
{
tail = newnode;
}
else
tail = tail.next = newnode;
}

static ListNode SegregatetoOddEVen()
{
while (curr!=null)
{
// Breaking the Link of the curr Node.
temp = curr;
curr = curr.next;
temp.next = null;

if (temp.val%2!=0) // If odd Node,append to odd LinkedList
{
oddTail.next = temp;
oddTail = temp;
}
else // If Even Node,append to even LinkedList
{
evenTail.next = temp;
evenTail = temp;
}
}
}

public static void main(String args[])
{
InsertatLast(1);
InsertatLast(2);
InsertatLast(3);
InsertatLast(4);
}
}``````

Output :