Dear reader, are you enjoying doing coding or not? Nevertheless, I welcome you to the new problem: 'Odd Even Linked List'.
Important Links : Problem link, Question Video, Solution Video
Dear reader, are you enjoying doing coding or not? Nevertheless, I welcome you to the new problem: 'Odd Even Linked List'.
Important Links : Problem link, Question Video, Solution Video
To understand the problem statement if you are not able to get it, I recommend you to watch the question video associated with this problem.
Let us maintain two linked lists, which are empty initially, named odd and even. At the end of the algorithm, odd should contain all the odd-valued elements, whereas the even should contain all the even-valued elements (both should be in the same order in which they appear in the original linked list).
Similar to what we did for Remove Duplicates in Sorted List, we will keep on removing the first node of the original linked list using removeFirst() method.
Now, if the element removed is odd-valued, then we will add a node with the same value at the end of odd using addLast() method.
Else, the element is even-valued, hence we will add a node with the same value at the end of even using addLast() method.
Finally, all the elements from the original linked list will be removed and will either be placed in the odd or even linked list.
Q) Are we preserving the original order among the odd elements and among the even elements?
R) Yes. Since, we are removing nodes one by one from the original linked list in order and placing them in the last of odd/even linked lists in the same order, hence we are able to preserve the relative ordering.
Now, there are three cases:
Please refer to the solution video if you find difficulty in understanding the algorithm completely.
Suggestion: Don't worry about how head and tail pointers will manage themselves in addLast(), removeFirst() functions. They were written by you only in previous problems, and now you are using them to solve more difficult problems. Clustering your thoughts around these functions can result in you failing in not coming up with an algorithm for the current problem statement.
Please I request you to give it a try before reading the code! Don't just blindly copy the code and submit it on any portal for the sake of completion. Doing so will not help you build an insight about Data Structures & Algorithms.
java; true";
This code is written and explained by our team in this video. Please refer to it if you are stuck somewhere. You should perform a dry run of the algorithm on some examples, to get a better understanding. It is also explained in the same video.
We are removing all nodes of original linked list one-by-one, which takes n * O(1) = O(n) time. Then, we are either adding them to odd linked list or the even linked list, which will again take n * O(1) = O(n) time.
Hence, the total time complexity = O(n + n) = O(2 * n) = O(n) only.
Similar to what we discussed in the previous problem, before adding a new node, we are REMOVING (deallocating space) a node from the original list, hence we are taking constant O(1) space.
We are starting with n nodes in the original linked list and empty odd/even lists, and finally we are getting an empty original linked list and n1 + n2 = n nodes in odd/even lists.
I hope you enjoyed solving the problem with me. I will bring another problem for you to solve, which is named 'K Reverse in Linked List'. Happy Coding!