Rearrange Odd and Even Places

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
50 upvotes
Asked in companies
OlaGoldman Sachs

Problem statement

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


Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
5
2 4 6 8 10


Sample Output 1:
2 6 10 4 8


Explanation Of Sample Input 1 :
The reordered list groups nodes with odd indices (2, 6, and 10) followed by nodes with even indices (4 and 8). So, the reordered list will look like: 2 -> 6 -> 10 -> 4 -> 8.


Sample Input 2 :
6
21 33 45 57 69 81


Sample Output 2 :
21 45 69 33 57 81


Explanation Of Sample Input 2 :
The reordered list groups nodes with odd indices (21, 45, and 69) followed by nodes with even indices (33, 57, and 81). Thus, the reordered list will appear as: 21 -> 45 -> 69 -> 33 -> 57 -> 81.


Constraints :
1 <= 'n' <= 5000
0 <= 'data' <= 10^4

Time Limit: 1 sec


Expected Complexity :
Time Complexity : O(n)
Space Complexity : O(1)
Hint

Can we make two pointers and then merge them?

Approaches (1)
2-pointer

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.
Time Complexity

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

 

We are just doing a linear traversal of the linked list. Hence, the final time complexity will be O(N). 

Space Complexity

O(1).

 

Since we are not using any extra space, the overall space complexity is O(1).

Code Solution
(100% EXP penalty)
Rearrange Odd and Even Places
Full screen
Console