![\"\"](\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1644926258084-112.Segregate%20even%20and%20odd%20nodes%20in%20a%20Linked%20List_Artboard%201.png\")
<\/p>\n<\/p>\n
This article taught a famous coding problem of a linked list i.e. Segregate even and odd nodes in a Linked List, this article will help you to grasp hands-on linked list problems. Let\u2019s take a look at the problem statement for a better understanding of Segregate even and odd nodes in a Linked List.<\/p>\n
In this problem, we are given a Linked List with even and odd valued nodes and are asked to segregate these nodes. Note that we also have to maintain the order in which the nodes were in the original linked list.<\/p>\n
Input Linked List:<\/strong> Output Linked List:<\/strong> Let’s try to understand the problem with help of an example:<\/p>\n By the way the statement Segregate even and odd nodes<\/strong> indicates that we need to rearrange the nodes of the linked list in such a way that all the even valued nodes appears before odd valued nodes in the modified linked list, and we also have to maintain the order in which the nodes were in the original linked list.<\/p>\n If our linked list is 1\u21922\u21923. Finally, our resultant segregated linked list will be 2\u21921\u21923.<\/p>\n If our linked list is 2\u21921\u21926\u21924\u21928. Finally, our resultant segregated linked list will be 2\u21926\u21924\u21928\u21921.<\/p>\n Now, I think from the above two examples that it is clear what we have to do in the problems.<\/p>\n Now the main question is how to approach this problem? Try to come up with some approach, not necessarily the optimized one but any approach (if It’s brute force it’s okay, no problem we will optimize it together).<\/p>\n Well, the most naive idea is to create a new Linked List by storing the values of the original Linked List and then inserting the nodes with even value first and then the nodes with odd values, but this will take extra space.<\/p>\n In the above approach we can see that we were able to solve the problem in O(n) time but space complexity is also O(n), so now we need to avoid this extra space.<\/p>\n Note:<\/strong> Generally whenever you get a question on an arrangement in a Linked List avoid dealing with data rather than try to think of a solution using the manipulation of links.<\/p>\n Let\u2019s try to think of some better approach.<\/p>\n The idea is to split the linked list into two parts containing only even nodes and the other containing only odd nodes. The only task then we will perform is to join these two linked lists together. Let\u2019s see this in algorithm form.<\/p>\n Traverse the linked list:<\/p>\n
\n![\"\"](\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/08\/57_1-01.png\")
<\/p>\n
\n![\"\"](\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/08\/57_2-01.png\")
<\/p>\n
\nThen, while segregating the even and odd nodes of the linked list:<\/p>\n\n
\nThen, while segregating the even and odd nodes of the linked list:<\/p>\n\n
Approach of Segregate even and odd nodes in a Linked List<\/h2>\n
Algorithm of Segregate even and odd nodes in a Linked List<\/h2>\n
\n
Dry Run of Segregate even and odd nodes in a Linked List<\/h3>\n
![\"\"](\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/08\/57_3-01-1.png\")
<\/p>\nCode Implementation of Segregate even and odd nodes in a Linked List<\/h2>\n\t\t\t\t\t\t