Last Updated: 7 Mar, 2021
Odd and even positioned linked list nodes
Easy
Asked in companies
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.
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
Approaches
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’
- If 'POS' is even, then.
- 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.
Consider 'HEAD' as the head of the linked list with odd nodes and ‘HEAD => NEXT’ as the head of the linked list with even nodes. Traverse the linked list after ‘HEAD => NEXT’, append odd nodes to 'HEAD', and even nodes to ‘HEAD => NEXT’. Now, 'HEAD' points to a linked list of odd nodes, and ‘HEAD => NEXT’ points to a linked list of even nodes. Point the last element of the linked list in 'HEAD' to ‘HEAD => NEXT’, to append even linked list after odd linked list. Return 'HEAD' 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.
- Initialize two pointers ‘oddNode = head’ and ‘EVEN_NODE = (HEAD => NEXT)’. Use ‘CUR_NODE’ to traverse the linked list. ‘oddNode’ and ‘EVEN_NODE’ store the last node of the odd and even linked list, respectively.
- Initialize two pointer EVEN_HEAD = (HEAD => NEXT)’ and ‘CUR_NODE = (EVEN_NODE=>NEXT)’.
- Initialize integer 'POS' to 1. Use 'POS' to check whether the current node is odd or even positioned.
- Run a loop until ‘CUR_NODE’ is not equal to ‘NULL’:
- If 'POS' is even, then.
- ‘(EVEN_NODE=>NEXT) = CUR_NODE’
- ‘EVEN_NODE = CUR_NODE’
- If 'POS' is odd, then.
- ‘(oddNode=>NEXT) = CUR_NODE’
- ‘oddNode = CUR_NODE’
- ‘CUR_NODE = (CUR_NODE=>NEXT)’
- ‘POS’ += 1’
- If 'POS' is even, then.
- ‘(ODD_NODE => NEXT) = EVEN_HEAD’
- ‘(EVEN_NODE=>NEXT) = NULL’
- Return 'HEAD' as the answer.