Odd and even positioned linked list nodes

Easy
0/40
Average time to solve is 10m
profile
Contributed by
50 upvotes
Asked in companies
Expedia GroupAmerican ExpressDream11

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
Full screen
Console