programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering OS Languages Paradigms IDEs Build Tools Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# Group all odd nodes together followed by the even nodes

Ranch Hand
Posts: 35
I found this question at http://www.programcreek.com/2015/03/leetcode-odd-even-linked-list-java/.
I debug the soltion and understood a bit. Here is the code:

My problem is I do not understand two parts:
1. Why ListNode connectNode = head.next; needed?
2. Why p1.next = connectNode; needed?

If we are changing the nodes towards the while loop than why need to connect them using connectNode. Are not they already connected?
Is there any better approach?

Sheriff
Posts: 11494
180
Yes, there's a better approach: Refactor the code and make it clearer.

Those are horribly cryptic names that can be replace with more expressive ones:

You need the firstEvenNode variable as a "bookmark" because the odd and even variables are your working variables that you use to traverse through the list. When you're done linking up all the odd numbered nodes, then you link the last odd node to the first even node that you bookmarked. On line 14, odd will point to the last odd node you added to the odd list so now you just have to link that node to the first even node, which is still referenced by firstEvenNode.

The additional hasAnother(Node) and nextOneOver(...) methods are convenience methods meant to help clarify the intent of the expressions someNode != null and the operation that links the current node to the node that's one position over, respectively. So if you had 1, 2, 3, 4, the node that's one over from 1 is 3 and the node that's one over from 2 is 4.

I hope this demonstrates to you how refactoring for clarity and choosing good variable/method names is essential to creating code that's more expressive and easier to understand.

This refactored code is still a little confusing, particularly lines 10 and 11. The reason this is not as clear as it could be is because the methods are static and procedural in nature. If you turned these methods into proper instance methods of the OddEven class, the code can be made more object-oriented, the code made simpler and clearer, and the abstraction much more intuitive.

I'll leave it to you as an exercise to make the code more object-oriented.

Junilu Lacar
Sheriff
Posts: 11494
180
A couple of small refactorings to make the code a little safer and more coherent. They're very small and subtle changes:

EDIT: That last term in the while loop on line 10 was really bugging me. It wasn't intuitive and I kept asking myself what it meant. So here's yet another refactoring for clarity:

The third check is needed so that the loop can handle both an odd and even number of nodes in the original list. Without it, you'd get a NullPointerException if you were reordering a list that had an odd number of nodes. The order of those checks is also significant. You have to check hasAnother(even) before you check hasAnother(after(even)).

The object-oriented version of this procedural code is so much better; there are no doubts as to what's happening in the OO version.

M Hasan
Ranch Hand
Posts: 35
Thanks. It was nice that you took your time to rewrite it.

Junilu Lacar
Sheriff
Posts: 11494
180
M Hasan wrote:Thanks. It was nice that you took your time to rewrite it.

I try not to pass up on any opportunity to practice refactoring and cleaning up code. I learn a lot from doing that.

Junilu Lacar
Sheriff
Posts: 11494
180
In case you're interested, this code in the procedural version:

becomes much clearer in the object-oriented version: