Intern

There is a wedding ceremony at NinjaLand. The bride and groom want everybody to play a game and thus, they have blindfolded the attendees. The people from the bride’s side are holding odd numbers and people from the groom’s side are holding the even numbers. For the game to start quickly, all the bride’s side people should come first, followed by the groom’s side people in the same order.

The attendees of the wedding with their numbers are given in the form of a Singly Linked List, arranged randomly.

A singly linked list is a type of linked list that is unidirectional; that is, it can be traversed in only one direction from head to the last node (tail).

Example:

The attendees holding numbers from 1, 4, 3 are shown: 

As the organizers are busy, you have to arrange all the people by arranging the bride’s side people first followed by the groom’s side people sequentially.

Note:

For the above example 1 -> 4 -> 3, 1 -> 3 -> 4 is the only correct answer, i.e nodes should be grouped sequentially. Hence, 3 -> 1 -> 4 is the wrong answer as we have to preserve the same order.

You are given a string 'STR'. The string contains [a-z] [A-Z] [0-9] [special characters]. You have to find the reverse of the string.

For example:

 If the given string is: STR = "abcde". You have to print the string "edcba".

follow up:

Try to solve the problem in O(1) space complexity.