Last Updated: 1 Dec, 2020
Rearrange Odd and Even Places
Moderate
Asked in companies
You are given the 'head' of a singly linked list. Your task is to group all the nodes with odd indices together followed by the nodes with even indices, and return the reordered list’s head.
The first node is considered odd, and the second node is even, and so on.
Note:
Keep in mind that reordering is to be done according to the indexes and not the node values.
Also, ensure that the relative order inside both the even and odd groups should remain as it was in the input.
Example:
Input: 'head' -> 1 -> 3 -> 5 -> 7
Output: 'head' -> 1 -> 5 -> 3 -> 7
Explanation:
The nodes with odd indices (1, 5) are grouped together, followed by the nodes with even indices (3, 7).
Input Format:
The first line contains an integer 'n' - the size of the linked list.
The second line contains 'n' space-separated integers, denoting the nodes of the linked list.
Output Format:
Return the 'head' of the reordered linked list.
Note:
You are not required to print the expected output; it has already been taken care of. Just implement the function.
Approaches
The idea is to maintain two pointers, one of which stores the list of nodes at odd positions and the other stores the list of nodes at an even position and then finally merge them.
The steps are as follows:
- Maintain a pointer ‘res’ which stores the final head, which we will return as the final result, also a pointer ‘evenHeadBegin’, which points to the beginning of the linked list of even positioned nodes.
- Maintain a pointer ‘oddHead’, which is used to tag along with the nodes at odd positions, similarly ‘evenHead’, which is used to tag along with nodes at even positions.
- Loop till ‘evenHead’ and next of ‘evenHead’ is not NULL:
- The ‘next’ pointer of ‘oddHead’should point to ‘next’ of ‘evenHead’
- Move the ‘oddHead’ pointer ahead.
- Similarly, now the ‘next’ pointer of ‘evenHead’ should point to the ‘next’ pointer of 'oddHead'.
- And then move the ‘evenHead’ pointer ahead.
- After exiting the loop, ‘oddHead’ next should point to ‘evenHeadBegin’ so that both linked lists are concatenated.
- Return ‘res’ as the final head of the newly formed linked list.