Partition List in 2 parts

Question

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;
}

Answer 1

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

Answer 2

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.