In this tutorial, I am going to discuss a programming question how to segregate even and odd nodes in a linked list or odd even linked list.
Given a singly linked list, We have to write a code to group all odd nodes together followed by the even nodes. We have to group based on node number not the value present in the node.
Try to solve this problem in O(n) time complexity and O(1) space complexity where n is the no. of nodes in a linked list.
Also, the relative order inside both the even and odd groups should remain as it was in the input. The first node is considered odd, the second node even and so on …
For example –
In the this example, Given input linked list is
1 -> 2 -> 3 -> 4 -> NULL
When we segregate even and odd nodes in a Linked List then the output is
1 -> 3 -> 2 -> 4 -> NULL