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

Odd and even positioned linked list nodes

Easy
0/40
Average time to solve is 10m
profile
Contributed by
48 upvotes
Asked in companies
Paytm (One97 Communications Limited)American ExpressExpedia Group

Problem statement

You are given a singly linked list ‘HEAD’ consisting of ‘N’ nodes. The task is to group all the odd nodes together, followed by the even nodes, maintaining the relative order of nodes given in the input. Note that we are talking about the node’s positions and not the value stored in the node. Try to write an in-place algorithm (i.e., without using any extra space) to solve this problem.

Example:
Given linked list: ‘2 => 1 => 3 => 4 => 6 => 5’

While maintaining the relative order of nodes as it is in the input, Nodes at odd positions are (2, 3, 6), and nodes at evens position are (1, 4, 5).

Modified linked list: ‘2 => 3 => 6 => 1 => 4 => 5’
Note:
1. Consider that the first node is odd, the second is even, and so on.
Detailed explanation ( Input/output format, Notes, Images )
Input format:
The first line of input contains an integer ‘T’ which denotes the number of test cases. Then, the ‘T’ test cases follow.

The first and only line of each test case 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.

For more clarity, please refer to the sample inputs. 
Output format:
For every test case, return the modified linked list.
Note:
You do not need to print anything; it has already been taken care of. Just implement the function.
Constraints:
1 <= T <= 100
1 <= N <= 10^3
-10^6 <= Node value <= 10^6 (Node Value != -1)  

Time limit: 1 second

Sample input 1:

2 
1 2 3 -4 5 6 -1    
-3 -1 

Sample output 1:

1 3 5 2 -4 6 -1
-3 -1 

Explanation of sample input 1:

Test Case 1:

Given linked list: ‘1 => 2 => 3 => -4 => 5 => 6’
While maintaining the relative order of nodes as it is in the input, Nodes at odd positions are (1, 3, 5), and nodes at evens position are (2, -4, 6). 
Modified linked list: ‘1 => 3 => 5 => 2 => -4 => 6’

Test Case 2:

Input linked list: ‘-3’
The linked list contains only one node.
Modified linked list: ‘-3’

Sample input 2:

2
3 5 -2 1 7 -1
-2 3 5 3 -1  

Sample output 2:

3 -2 7 5 1 -1
-2 5 3 3 -1
Hint

Try to store the required sequence of nodes in another data structure.

Approaches (2)
Use an array.

Create an array ‘RESULT’ of size 'N' to store addresses of nodes. The number of odd nodes in the linked list is equal to ‘ceil(n/2)’ (‘ceil(x)’: Smallest possible integer value greater than or equal to ‘x’). Traverse the linked list and insert the odd nodes into ‘RESULT’ from index 0 and the even nodes from index ‘ceil(n/2)’. Now, ‘RESULT’ stores all the odd nodes together, followed by even nodes. We need to modify the nodes’ sequence in the linked list to that of ‘RESULT’. To do that, traverse the array ‘RESULT’, and for each position ‘i’ in ‘RESULT’, make node at ‘RESULT[i]’ point to the node at ‘RESULT[i+1]’. Return ‘HEAD’ (which is the same as ’RESULT[0]) as the answer.

 

  • If ‘HEAD’ is equal to ‘NULL’ or ‘HEAD=>next’ is equal to ‘NULL’, then return ‘HEAD’. There is no need to modify the linked list if it contains less than two nodes.
  • Find the length of the linked list and store it in integer 'N'.
  • Create an array ‘RESULT’ of size 'N' to store linked list nodes’ addresses.
  • Initialize pointer ‘CURR_NODE’ to ‘HEAD’. Use it to traverse the linked list.
  • Initialize integers 'POS' to 1, 'ODD_POS' to 0 and ‘evenPos’ to ‘ceil(n/2). Use 'ODD_POS' and ‘evenPos’ as indexes to the starting position of odd and even nodes in ‘RESULT’.
  • Run a loop until ‘curNode’ is not equal to ‘NULL’:
    • If 'POS' is even, then.
      • ‘RESULT[evenPos] = curNode’
      • ‘evenPos += 1’
    • If 'POS' is odd, then.
      • ‘RESULT[oddPos] = curNode’
      • ‘oddNode += 1’
    • ‘CUR_NODE = (CUR_NODE => NEXT)’
    • ‘POS += 1’
  • Run a loop where ‘i’ ranges from 0 to ‘n-2’:
    • ‘(RESULT[i]=>next) = RESULT[i + 1]’
  • ‘RESULT[N - 1] = NULL’
  • Return ‘HEAD’ as the answer.
Time Complexity

O(N), where ‘N’ is the length of the input linked list. 

 

We traverse the input linked list and the array ‘RESULT’ once, both having length ‘N’.

Space Complexity

O(N), where ‘N’ is the length of the input linked list. 

 

We created an array ‘RESULT’ of size ‘N’. So, we require ‘O(N)’ space.

Code Solution
(100% EXP penalty)
Odd and even positioned linked list nodes
All tags
Sort by
Search icon

Interview problems

Python easy solution

def oddEvenLinkedList(head):
    odd=head
    even=head.next
    evenhead=even
    while even!=None and even.next!=None:
        odd.next=odd.next.next
        even.next=even.next.next
        
        odd=odd.next
        even=even.next
        
    odd.next=evenhead
    return head
1 view
0 replies
0 upvotes
profile

Interview problems

c++

Node *oddEvenLinkedList(Node *head) {

  // Write your code here.

  Node *odd = head->next;

  Node *a = head;

  Node *b = a->next;

  while (b && b->next) {

    a->next = b->next;

    a = a->next;

    b->next = a->next;

    b = b->next;

  }

  a->next = odd;

  return head;

}

12 views
0 replies
0 upvotes

Interview problems

easy python

def oddEvenLinkedList(head):

 

    if head==None or head.next==None:

        return head

    odd=head

    even=head.next

    temp=even

    while even and even.next:

        odd.next=odd.next.next

        odd=odd.next

        even.next=even.next.next

        even=even.next

    odd.next=temp

    return head

2 views
0 replies
0 upvotes

Interview problems

easy cpp

Node *oddEvenLinkedList(Node *head) {

    // Write your code here.

    if(head->next==NULL) return head;

    Node* join=head->next;

    Node* t1=head;

    int count=0;

    while(t1!=NULL && t1->next!=NULL && t1->next->next!=NULL){

        count++;

        Node* temp=t1->next;

        t1->next=t1->next->next;

        t1=temp;

    }

    if (count%2!= 0) {

        Node *last = t1->next;

        last->next = join;

        t1->next = NULL;

    }else{

        Node *last = t1->next;

        last->next = NULL;

        t1->next = join;

    }

    return head;

}

71 views
0 replies
1 upvote

Interview problems

C++ solution easy

 

Node *oddEvenLinkedList(Node *head) 

{

    if(head==NULL || head->next==NULL ||head->next->next==NULL)

           return head;

    Node* oddstart=head;

    Node* evenstart=head->next;

    Node* temp=evenstart;

    while(evenstart !=NULL && evenstart->next !=NULL)

    {

        oddstart->next=oddstart->next->next;

        oddstart=oddstart->next;

        evenstart->next=evenstart->next->next;

        evenstart=evenstart->next;

    }

      oddstart->next=temp;

      return head; 

}

70 views
0 replies
0 upvotes

Interview problems

Simplest Cpp code|O(n) |4 line code

Node *oddEvenLinkedList(Node *head) {

    // Write your code here.

   if(head==NULL||head->next==NULL) return head;

    Node *odd=head,*even=head->next,*d=head->next;

    

    while(odd->next&&even->next)

    {

       odd->next=odd->next->next;

       odd=odd->next;

        

       even->next=even->next->next;

       even=even->next;

    }

    odd->next=d;

    return head;

}

58 views
0 replies
1 upvote

Interview problems

Easy Java Solution

public class Solution {
	public static Node oddEvenLinkedList(Node head) {
		// Write your code here.
		if (head == null || head.next == null) {
            return head;
        }

        // Initialize pointers for odd and even sublists
        Node oddHead = head;
        Node evenHead = head.next;
        Node oddTail = oddHead;
        Node evenTail = evenHead;
        Node curr = evenHead.next;
        int position = 3; // Start from the third node (1-based index)

        // Traverse the list and separate odd and even nodes
        while (curr != null) {
            if (position % 2 == 1) { // Odd position
                oddTail.next = curr;
                oddTail = curr;
            } else { // Even position
                evenTail.next = curr;
                evenTail = curr;
            }
            curr = curr.next;
            position++;
        }

        // Connect the last node of the odd sublist to the head of the even sublist
        oddTail.next = evenHead;
        evenTail.next = null; // Set the next of the last even node to null

        return oddHead;
	}
}
52 views
0 replies
0 upvotes

Interview problems

EASY C++ CODE

Node *oddEvenLinkedList(Node *head) {

    if(head == NULL){

        return head;

    }

    Node* odd = head; //first position is odd

    Node* even = head->next; //second position

 

    Node* evenHead = even; //making head for even LL

 

    while(even != NULL && even->next != NULL){

        //change pointer of nodes at ODD index

        odd->next = odd->next->next;

        odd = odd->next;

 

        //similarly for nodes at even positon

        even->next = even->next->next;

        even = even->next;

 

    }

    //after that join evenhead to odd

        odd->next = evenHead;

        return head;

}

225 views
0 replies
2 upvotes

Interview problems

C++ Easy

Node *oddEvenLinkedList(Node *head) 

{

    if(head==NULL || head->next==NULL ||head->next->next==NULL)

    return head;

    Node* oddstart=head;

    Node* evenstart=head->next;

    Node* temp=evenstart;

    while(evenstart !=NULL && evenstart->next !=NULL)

    {

        oddstart->next=oddstart->next->next;

        oddstart=oddstart->next;

        evenstart->next=evenstart->next->next;

        evenstart=evenstart->next;

    }

      oddstart->next=temp;

      return head; 

}

79 views
0 replies
0 upvotes

Interview problems

Easy C++ Solution

Node* oddEvenLinkedList(Node* head) {

    if (!head || !head->next || !head->next->next) {

        return head;

    }

 

    Node* odd = head;

    Node* even = head->next;

    Node* evenHead = even;

 

    while (even && even->next) {

        odd->next = even->next;

        odd = odd->next;

        even->next = odd->next;

        even = even->next;

    }

 

    odd->next = evenHead;

    return head;

}

129 views
0 replies
0 upvotes
Full screen
Console