LeetCode 328: Odd Even Linked List in Java
LeetCode 328. Odd even Linked List | Java
Created and recorded by Aman Chhina. June 2021
Overview
1. Understand the problem.
2. Visualize the problem.
3. Visualize the solution.
4. Code our solution.
Link to Problem: https://leetcode.com/problems/odd-eve...
Introduction to the problem, and clarifying the grouping of odd/even is by index and not by value of the linked list.
After understanding what the problem is asking let us try visualizing the problem by drawing it out. Now that we can see how we are meant to rearrange the nodes in our linked list, let us try splitting our linked list into an odd list and even list. We then can see we will need a reference to the head of our odd and even linked list, as well as a tail to them as well. We now iterate over our original linked list and append the current node to the end of the odd list or even list depending on if we are at an odd/even index which we will keep track of through a boolean variable. Once we have walked through the example let us mention some edge cases to consider, such as the even tail next being pointed to null otherwise, our newly created linked list will contain a cycle. Then we mention how we do not want to include the reference heads for our odd or even linked list but just the nodes in the list itself. Thus, we attach the end of our odd linked list to the node after the head in the even linked list, and finally return the node after odd linked list as our answer.
We now code the solution for our visualization, in which we declare the reference heads and tails for our odd and even linked lists, and a boolean variable odd which dictates whether we are at an odd index or not (which by default means we are at an even index). Run our solution and we can see it passes all the test cases and runs 100% faster than all other Java solutions.
