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 maintained in modified LinkedList. Example 2: Input: 1→3→5→Null Output: 1→3→5→Null Explantion: As there are no Even Nodes in LinkedList, The Modified LinkedList is same as Original LinkedList. Example 3: Input: 2→4→6→8→Null Output: 2→4→6→8→Null Explanation: As there are no Odd Nodes in LinkedList, The Modified LinkedList is same as Original 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 :
Original LinkedList
Creation of Heads for Even and Odd LinkedList
‘
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
Appending OddLinkedList at End of Even LinkedList
Modified 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;
}
};
ListNode *head, *tail; // head and tail of the LinkedList
void PrintList(ListNode *head) // Function to print the LinkedList
{
ListNode *curr = head;
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);
if (head == nullptr)
head = newnode, tail = newnode;
else
tail = tail->next = newnode;
}
ListNode *SegregatetoOddEVen()
{
// creating Heads of Odd and Even LinkedLists
ListNode *oddHead = new ListNode(-1), *oddTail = oddHead;
ListNode *evenHead = new ListNode(-1), *evenTail = evenHead;
ListNode *curr = head, *temp;
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;
}
}
evenTail->next = oddHead->next;
// Appending Odd LinkedList at end of EvenLinkedList
return evenHead->next;
}
int main()
{
InsertatLast(1);
InsertatLast(2);
InsertatLast(3);
InsertatLast(4);
cout << "Initial LinkedList : " << endl;
PrintList(head);
ListNode *newHead = SegregatetoOddEVen();
cout << "LinkedList After Segregration " << endl;
PrintList(newHead);
return 0;
}
Output :
Initial LinkedList :
1→2→3→4→null
LinkedList After Segregration
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{
static ListNode head, tail; // head and tail of the LinkedList
static void PrintList(ListNode head) // Function to print the LinkedList
{
ListNode curr = head;
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);
if (head == null)
{
head = newnode;
tail = newnode;
}
else
tail = tail.next = newnode;
}
static ListNode SegregatetoOddEVen()
{
// creating Heads of Odd and Even LinkedLists
ListNode oddHead = new ListNode(-1), oddTail = oddHead;
ListNode evenHead = new ListNode(-1), evenTail = evenHead;
ListNode curr = head, temp;
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;
}
}
evenTail.next = oddHead.next;
// Appending Odd LinkedList at end of EvenLinkedList
return evenHead.next;
}
public static void main(String args[])
{
InsertatLast(1);
InsertatLast(2);
InsertatLast(3);
InsertatLast(4);
System.out.println("Intial LinkedList : ");
PrintList(head);
ListNode newHead = SegregatetoOddEVen();
System.out.println("LinkedList After Segregration ");
PrintList(newHead);
}
}
Output :
Initial LinkedList :
1→2→3→4→null
LinkedList After Segregration
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.
Special thanks to SaiSri Angajala for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article