4
\$\begingroup\$

I came up with the following code while trying to solve the Leetcode partition list problem

Though my solution is accepted, I am not happy with a few of the additional variables which I am creating. In the code below, I would like to avoid creation of tailEnd and headEnd variables somehow.

Can you please review the code and suggest a better way to write this code.

public ListNode partition(ListNode head, int x) {
    ListNode partitionHead = null;
    ListNode partitionTail = null;
    ListNode headEnd = null;
    ListNode tailEnd = null;

    ListNode node = head;

    while (node != null) {
        if (node.val <x ) {
            if (partitionHead == null) {
                partitionHead = node;
            } else {
                headEnd.next = node;
            }
            headEnd = node;
        } else {
            if (partitionTail == null) {
                partitionTail = node;
            } else {
                tailEnd.next = node;
            }
            tailEnd = node;
        }
        node = node.next;
    }

    if (tailEnd != null) {
        tailEnd.next = null;
    }

    if (partitionHead == null) {
        return partitionTail;
    }

    headEnd.next = partitionTail;

    return partitionHead;
}
\$\endgroup\$
3
  • 1
    \$\begingroup\$ Looks nice; my only thought would be the while could be better expressed as for (ListNode node = head; node != null; node = node.next) { \$\endgroup\$
    – racraman
    Commented Jul 23, 2022 at 1:03
  • \$\begingroup\$ Can you copy-paste the problem description to the question? Leetcode isn't responding to me (and to make sure the eventual downfall of the site will not make this post useless). \$\endgroup\$ Commented Aug 2, 2022 at 12:09
  • \$\begingroup\$ leetcode often pushes you into creating solutions, that "only work" but mostly lack the quality of real software craftmanship - but i love these exercises :-) \$\endgroup\$ Commented Aug 5, 2022 at 17:59

2 Answers 2

2
\$\begingroup\$

violation of the IOSP

it would have helped me greatly to understand your code if you had applied the clean code rule of IOSP:

IOSP calls for a clear separation:

  • Either a method contains exclusively logic, meaning transformations, control structures or API invocations. Then it’s called an Operation.
  • Or a method does not contain any logic but exclusively calls other methods within its code basis. Then it’s called Integration.

what i would have expected:

if(isBelowThreshold(currentNode)){
    pushToHead(currentNode );
}else{
    pushToTail(currentNode);
}
currentNode = getNext();

what i actually received:

if (node.val <x ) {
    if (partitionHead == null) {
        partitionHead = node;
    } else {
        headEnd.next = node;
    }
    headEnd = node;
} else {
    if (partitionTail == null) {
        partitionTail = node;
    } else {
        tailEnd.next = node;
    }
    tailEnd = node;
}
node = node.next;

IOSP is super simple and super valuable, it:

  • splits your code into testable methods
  • increases readability and reduces complexity
  • makes your code easier to change (just add a step or remove one or change order)

if you need more inspiriation about read this article

\$\endgroup\$
1
\$\begingroup\$

Simplify conditionals for possibly null head using dummy variables

The algorithm of the posted code is very nice and simple, congratulations. What makes it a bit difficult to understand is the many conditionals for the potential null heads. A nice trick in situations like this is using a dummy variable that points to the head. This lets you work with nodes that are guaranteed to not be null, for example:

public ListNode partition(ListNode head, int x) {
    var dummyLeft = new ListNode();
    var dummyRight = new ListNode();
    
    var left = dummyLeft;
    var right = dummyRight;
    for (var node = head; node != null; node = node.next) {
        if (node.val < x) {
            left.next = node;
            left = left.next;
        } else {
            right.next = node;
            right = right.next;
        }
    }
    
    left.next = dummyRight.next;
    right.next = null;
    return dummyLeft.next;
}

Limit variables to the minimal necessary scope

The node variable is only needed in the loop body. So it's nice to use a for loop, to avoid the mistake of accidentally using it outside of the loop.

Use better names

Since there are multiple lists involved inside the function, the terms "head" and "tail" can be confusing. That's why I used "left" and "right" instead in the above example code.

Use var

Modern Java supports the var keyword, and it helps to type less (no pun intended) where the variable type is clear enough.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.