Odd Even Linked List

#computerscience #100daysofcode #java

Linked list problems can seem tricky at first, but they aren’t so bad once you get the hang of them. Or so they say. I have yet to get to that point, which is why I am here blogging about it! If you are brand new to linked lists then check out this post. While, reversing linked lists and finding cycles are great problems to start on, this odd even linked list problem is a pretty good one for us beginners as well. Let’s get started!

The Problem

Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.

Link to Problem

Check out Figure A for an example input and result.

Figure A

How to Solve

For this problem, we are going to create two linked lists. One of the linked lists will contain all of the odd nodes from the original list and the other list will contain all of the even nodes from the original list. Once we have these two lists, the even list will get added on to the end of the odd list.

In this example the list nodes just happen to have values that correspond to their placement in the list. Just a reminder that the problem states that “we are talking about the node number and not the value in the nodes”.

The Code

Let’s take a look at the code to solve this problem. Read through the code and make as much sense of it as possible. Then we can go through it step-by-step and make sure that we understand it completely.

Here are the steps that the algorithm takes:

Create 5 new nodes: oddHead, evenHead, oddNode, evenNode, and current.
oddHead and evenHead do not move during this algorithm. They will keep track of the beginning of the odd and even lists.
Current iterates through the nodes of the list until it reaches null. At each iteration of current, the node that current points to will either be connected to the end of the odd list or the even list.
Once current reaches null, the even list will get connected to the end of the odd list.

Some Illustrations

I know what might be helpful! How about we use some illustrations to help us better understand what is going on in the algorithm.

Take a look at Figure B. It shows what happens in lines 15–21 of the code. This can be thought of as a preparatory step. It is common for linked list problems to have a preparatory step like this. I also want to mention that head is still pointing to the first node. It just isn’t shown to make things a bit clearer.

Figure B

Figure C shows what happens in lines 23–25 of the code. oddNode.next is set to current, current points to the next node, and oddNode now points to where current just was. Also notice that oddHead stays in the same spot.

Figure C

Figure D show what happens in lines 27–29 of the code. evenNode.next is set to current, current points to the next node, and evenNode now points to where current just was. Once again, notice that evenHead stays in the same spot.

Figure D

In Figure E we are back to lines 23–25 of the code. oddNode.next is set to current, current points to the next node, and oddNode now points to where current just was. Take note that current now points to NULL.

Figure E

In Figure F only lines 27–28 of the code are applied because current = NULL. evenNode.next is set to current and evenNode points to where current is. current = NULL and the while loop terminates.

Figure F

Now on to line 32 of the code. oddNode.next is set to evenHead, which results in the even list being added to the end of the odd list. The original head has been brought back just in case you forgot it was still there.

Figure G

Output:

result: [1, 3, 5, 2, 4]

Time Complexity

This algorithm will have a time complexity of O(n) with n being the number of nodes in the linked list.

Space Complexity

The algorithm runs in constant space O(1).

Want to know more about Big-O? I know of a great place to start.

Get Better at Algorithms!

Algorithms and data structures are pretty tough. They are definitely taking a while for me to get the hang of them. However, there are some great resources out there, and I feel obligated to share some that have been most helpful to me. If I missed any that have been helpful to you, be sure to mention them in the comments.

Cracking the Coding Interview — Great resource. Really gets you in the right mindset for interviews. You can find it here.
Elements of Programming Interviews — Another great book. Personally, I like this one more than CTCI, but YMMV. You can find it here.
Grokking the Coding Interview — Can’t emphasize this one enough. Haven’t seen it mentioned it too often. Explains patterns that occur in different coding challenge problems. Great at providing a big-picture of all the different algorithm problems you might encounter. Check it out here.
Back To Back SWE — Great YouTube Channel. Highly recommend.
Kevin Naughton Jr. — Another awesome YouTube channel. Great at going over problems and gives helpful advice.
Base CS — Vaidehi Joshi does a great job of laying out the fundamentals of algorithms and data structures. Check out the blog series here. She also has a podcast that I give two thumbs up.
Coding Challenge Website — There are plenty of different ones to choose from. HackerRank, CodeWars, and Edabit all seem to be pretty popular. I personally use LeetCode. Find the one that works for you!
Pramp — Do mock interviews! The sooner the better! Pramp has been a huge help to me.