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

Last Updated: 7 Mar, 2021

Easy

```
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’
```

```
1. Consider that the first node is odd, the second is even, and so on.
```

```
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.
```

```
For every test case, return the modified linked list.
```

```
You do not need to print anything; it has already been taken care of. Just implement the function.
```

```
1 <= T <= 100
1 <= N <= 10^3
-10^6 <= Node value <= 10^6 (Node Value != -1)
Time limit: 1 second
```

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’**

**‘(ODD_NODE => NEXT) = EVEN_HEAD’****‘(EVEN_NODE=>NEXT) = NULL’****Return 'HEAD' as the answer.**

Similar problems

Deletion In Doubly Linked List

Easy

Posted: 22 Apr, 2022

Deletion In Doubly Linked List

Easy

Posted: 22 Apr, 2022

Insertion In Doubly Linked List

Easy

Posted: 24 Apr, 2022

Insertion In Doubly Linked List

Easy

Posted: 24 Apr, 2022

LRU Cache

Moderate

Posted: 10 Sep, 2022

Delete Nodes On Regular Intervals

Ninja

Posted: 19 Dec, 2022

Add One To Linked List

Hard

Posted: 19 Dec, 2022