Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Segregate Even And Odd Nodes In a Linked List

Easy
0/40
Average time to solve is 15m
profile
Contributed by
89 upvotes
Asked in companies
OlaPaytm (One97 Communications Limited)Dunzo

Problem statement

You are given the head node of a singly linked list 'head'. Your task is to modify the linked list in such a way that all the even valued nodes appear before the all odd valued node and order of nodes remain the same.


Example :-
The given singly linked list is  6 -> 5 -> 3 -> 4 -> 7 -> 1 -> 2 

subsequence

The modified linked list should have all even values in starting and odd values in the end.
Detailed explanation ( Input/output format, Notes, Images )
Input Format :-
The first line contains space-separated integers denoting the values of nodes of the Linked List. The Linked List is terminated with -1. Hence, -1 is never a node value of the Linked List.
Output Format :-
Print space-separated integers denoting the elements of the modified linked list.
Note :-
You do not need to print anything; it has already been taken care of. Just implement the given function.
Sample Input 1
2 1 3 5 6 4 7 -1
Sample Output 1
2 6 4 1 3 5 7
Explanation of Sample Input 1
Given singly linked list 2 -> 1 -> 3 -> 5 -> 6 -> 4 -> 7.

Arrange all the even values in the starting and odd values at the end of the linked list.

So ‘2, 6, 4’ must appear in the starting and ‘1, 3, 5, 7’ must appear at the end of linked list 

So return 2 -> 6 -> 4 -> 1 -> 3 -> 5 -> 7
Sample Input 2
6 5 4 3 2 1 -1
Sample Output 2
6 4 2 5 3 1
Constraints :-
1 <= 'N' <= 5000
0 <= node value <= 10^9  

Where ‘N’ is the number of nodes in the linked list.

Time Limit: 1 sec
Hint

Try to divide the linked list into two parts.

Approaches (1)
Brute Force Approach

The basic idea is to divide the linked list into two parts - odd and even. The even linked list will contain only nodes whose value is even and vice - versa for the odd linked list. Finally, we will attach the odd linked list after the even linked list.

 

Algorithm

 

  • Use four pointers ‘evenStart =null’, ‘oddStart =null’, ‘evenLast =null’, ‘oddLast =null’.
  • Copy the ‘head’ of the linked list in ‘current= head’ variable.
  • Iterate the linked list while it’s not null:
    • Let our current node be ‘currVal’. Then ‘currVal= current->val’.
    • If ( currVal %2==0 ), then it is a part of the even values linked list.
      • if( evenStart==null) then it is the first node of the even values linked list.
        • We set the variables ‘evenStart= current’ and ‘evenEnd= evenStart’
      • Else, even values linked list has already some nodes so-
        • Add ‘evenEnd ->next =current’ and ‘evenEnd= evenEnd’
  • Else then it is a part of odd values linked list.
    • if( oddStart==null) then it is the first node of odd values linked list.
      • We set the variables ‘oddStart= current’ and ‘oddEnd= oddStart’
    • Else, odd linked list has already some nodes so-
      • Add ‘oddEnd ->next =current’ and ‘oddEnd= oddEnd’
  • Now we have created two even and odd separate linked list(ll),
  • if(oddStart == null or evenStart == null), it means we don't need to do anything just return the linked list ‘head’.
  • Else concatenate the both even and odd linked list with ‘head’ by-
    • evenEnd ->next = oddStart
    • oddEnd -> next = null
    • head= endStart
  • We finally return ‘head’
Time Complexity

O(N), Where ‘N’ is the size of the given singly linked list.

 

As every element of the linked list will be visited at most one the time complexity will be O(N).

Space Complexity

O(N), Where ‘N’ is the size of the given singly linked list.

 

As every element of the linked list will be copied into ‘evenStart’ or ‘oddStart’ the space complexity will be O(N).

Code Solution
(100% EXP penalty)
Segregate Even And Odd Nodes In a Linked List
All tags
Sort by
Search icon

Interview problems

Very Easy Solution By NK

/*

 * Definition for linked list.

 * class Node {

 *  public:

 *      int data;

 *      Node *next;

 *      Node() : data(0), next(nullptr) {};

 *      Node(int x) : data(x), next(nullptr) {}

 *      Node(int x, Node *next) : data(x), next(next) {}

 * };

 */

 

void insertAtEnd(Node* &tail,int data){

    Node* newNode=new Node(data);

    tail->next=newNode;

    tail=newNode;

}

Node* segregateEvenOdd(Node* head)

{

    // Write your code here

    Node* evenHead=new Node(-1);

    Node* evenTail=evenHead;

    Node* oddHead=new Node(-1);

    Node* oddTail=oddHead;

 

    Node* temp=head;

    while(temp){

        if(temp->data %2==0){

            insertAtEnd(evenTail,temp->data);

        }

        else{

            insertAtEnd(oddTail,temp->data);

        }

        temp=temp->next;

    }

 

    evenHead=evenHead->next;

    evenTail->next=oddHead->next;

    return evenHead;

}

 

25 views
0 replies
1 upvote

Interview problems

Efficient Python O(N) Single Traversal Solution

# Following is the structure of the Node class already defined:

class node:
    def __init__(self, data):
        self.data = data
        self.next = None

def segregateEvenOdd(head):
    oddNode = node(-1)
    evenNode = node(-1)
    even_curr = evenNode
    odd_curr = oddNode
    curr = head
    
    while curr:
        if curr.data % 2 == 0:
            even_curr.next = curr
            even_curr = even_curr.next

        else:
            odd_curr.next = curr
            odd_curr = odd_curr.next

        curr = curr.next
    
    # Terminate both lists
    even_curr.next = None
    odd_curr.next = None
    
    even_curr.next = oddNode.next
    return evenNode.next
44 views
0 replies
0 upvotes

Interview problems

C++ solution || 82% efficiency

Node* segregateEvenOdd(Node* head)
{
    if(head == nullptr) return head;
    Node* evenHead = nullptr;
    Node* evenTail = nullptr;
    Node* oddHead = nullptr;
    Node* oddTail = nullptr;
    Node* current = head;

    while(current){
        if(current->data%2==0){
            if(evenHead==nullptr){
                evenHead=current;
                evenTail=evenHead;
            }else{
                evenTail->next=current;
                evenTail=evenTail->next;
            }
        }
        else{
            if(oddHead==nullptr){
                oddHead=current;
                oddTail=oddHead;
            }
            else{
              oddTail->next=current;
              oddTail=oddTail->next;  
            }
        }
        current=current->next;
    }

    //endlist
    if(evenTail!=nullptr) evenTail->next=nullptr;
    if(oddTail!=nullptr) oddTail->next=nullptr;

    //output both together - merge
    if(evenHead==nullptr) return evenHead;
    if(oddHead==nullptr) return oddHead;

    evenTail->next=oddHead;

    return evenHead;

}
136 views
0 replies
0 upvotes

Interview problems

Segregate Even And Odd Nodes In a Linked List using Dummy node approach

 

class Node:

def __init__(self, data):

self.data = data

self.next = None

 

def segregateEvenOdd(head):

# Write your code here

if head is None or head.next is None:

return head

 

odd = Node(-1)

oddHead = odd

even = Node(-1)

evenHead = even

curr = head

 

while curr:

if curr.data % 2 == 1:

odd.next = curr

odd = odd.next

else:

even.next = curr

even = even.next

curr = curr.next

 

odd.next = None

even.next = None

 

if oddHead.next and evenHead.next:

head = evenHead.next

even.next = oddHead.next

elif oddHead.next and evenHead is None:

head = oddHead.next

else:

head = evenHead.next

 

return head

53 views
0 replies
0 upvotes

Interview problems

java solution

public class Solution

{

    public static Node segregateEvenOdd(Node head)

    {

        // Write Your Code Here.

         if (head == null || head.next == null) {

            return head; // No need to segregate if there's 0 or 1 node

        }

 

        Node evenHead = new Node(0); // Dummy node for even values

        Node oddHead = new Node(0); // Dummy node for odd values

        Node evenTail = evenHead; // Pointer to the tail of the even list

        Node oddTail = oddHead; // Pointer to the tail of the odd list

 

        Node current = head;

        while (current != null) {

            if (current.data % 2 == 0) {

                // Even node, append to even list

                evenTail.next = current;

                evenTail = evenTail.next;

            } else {

                // Odd node, append to odd list

                oddTail.next = current;

                oddTail = oddTail.next;

            }

            current = current.next;

        }

 

        // Concatenate the even list and odd list

        evenTail.next = oddHead.next;

        // Make sure to mark the end of the odd list

        oddTail.next = null;

 

        // Return the head of the modified list

        return evenHead.next;

    }

}

69 views
0 replies
0 upvotes

Interview problems

EASY JAVA SOLUTION

public static Node segregateEvenOdd(Node head)

{

Node evenList = null;

Node evenP = null;

 

Node oddList = null;

Node oddP = null;

 

Node temp = head;

 

while(temp!=null){

if(temp.data%2==0){

if(evenList == null){

evenList = temp;

evenP=evenList;

}else{

evenP.next = temp;

evenP = evenP.next;

}

}else{

 

if(oddList == null){

oddList = temp;

oddP=oddList;

}else{

oddP.next = temp;

oddP = oddP.next;

}

 

}

temp = temp.next;

}

oddP.next=null;

evenP.next=oddList;

return evenList;

}

}

72 views
0 replies
0 upvotes

Interview problems

Segregate Even And Odd Nodes In a Linked List

Node* segregateEvenOdd(Node* head) {    // Write your code here    if(head == NULL || head->next == NULL){        return head;    }    Node* temp = head;    vector<int> a;    while(temp){        a.push_back(temp->data);        temp = temp->next;    }    vector<int> even;    vector<int> odd;    for(int i=0; i<a.size(); i++){        if(a[i]&1){            odd.push_back(a[i]);        }        else{            even.push_back(a[i]);        }    }    for(int i=0; i<odd.size(); i++){        even.push_back(odd[i]);    }

   int i=0;    temp = head;    while(temp){        temp->data = even[i];        i++;        temp = temp->next;    }

   return head; }

179 views
0 replies
0 upvotes

Interview problems

best solution in java tc-->O(n) && sc-->O(1) by using pointers

public class Solution
{
    public static Node segregateEvenOdd(Node head)
    {
        // Write Your Code Here.
        if(head==null || head.next==null){
            return head;
        }
        Node temp =head;
        Node even=null;
        Node even_temp=null;
        Node odd_temp=null;
        Node odd=null;
        while(temp!=null){
            if(temp.data%2==0){
                if(even==null){
                    even=temp;
                    even_temp=even;
                }
                else{
                    even_temp.next=temp;
                    even_temp=even_temp.next;
                }
            }
            else{
                if(odd==null){
                    odd=temp;
                    odd_temp=odd;
                }else{
                    odd_temp.next=temp;
                    odd_temp=odd_temp.next;
                }
            }
            temp=temp.next;
        }
        odd_temp.next=null;
        even_temp.next=odd;
        return even;
    }
}
186 views
0 replies
0 upvotes

Interview problems

Segregate Even And Odd Nodes In a Linked List

'''
Following is the structure of the Node class already defined:


class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


'''


def segregateEvenOdd(head):


    if head is None:
        return None
    
    even_head = None
    even_tail = None
    odd_head = None
    odd_tail = None
    
    current = head
    
    while current:
        if current.data % 2 == 0:
            if even_head is None:
                even_head = current
                even_tail = even_head
            else:
                even_tail.next = current
                even_tail = even_tail.next
        else:
            if odd_head is None:
                odd_head = current
                odd_tail = odd_head
            else:
                odd_tail.next = current
                odd_tail = odd_tail.next
        current = current.next
    
    if even_tail:
        even_tail.next = odd_head
    else:
        even_head = odd_head
    
    if odd_tail:
        odd_tail.next = None
    
    return even_head

python

134 views
0 replies
0 upvotes

Interview problems

Optimal Approach using CPP, TC: O(n) and SC: O(1)

Node* segregateEvenOdd(Node* head)
{
	
    //TC: O(n) and SC: O(1)
    //create to dummy node name oddNode and evenNode
    //create to pointer of it name odd and even
    if(head==nullptr || head->next==nullptr) return head;
    Node* oddNode = new Node(-1);
    Node* evenNode = new Node(-1);
    Node* odd = oddNode;
    Node* even = evenNode;
    Node* temp = head; // for iterating in linkedlist
    while(temp){
        //condition 
        if((temp->data)%2==0){
            even->next = temp;
            even = even->next;
        }else{
            odd->next = temp;
            odd = odd->next;
        }
        temp = temp->next;
    }
    odd->next = nullptr;
    if(oddNode->next) even->next = oddNode->next;
    delete oddNode;
    return evenNode->next;

}
//Kindly upvote,if this helped you in anyway
//It keeps me motivated to help other and grow
//Thanks in Advance!!
319 views
0 replies
2 upvotes
Full screen
Console