CODEWITHSUNDEEP
javalinked-list
Chris Huynh
Chris Huynh

Reputation: 21

Why can't I just do node = node.next to iterate through linked list?

I am currently doing a Cracking the Coding Interview Problem (2.4) and I am supposed to partition a linked list around a value x, such that all nodes less than x come before all nodes greater than or equal to x. However, I am really confused as to why a temporary variable "next" is needed and why is node.next nulled below it. Why can't I just do node = node.next at the end of the while loop?

I am simply creating two linked lists, before and after, and merging them together once the correct values are put into each list.

public static Node partition(Node node, int x) {
    Node beforeStart = null;
    Node beforeEnd = null;
    Node afterStart = null;
    Node afterEnd = null;

    /* Partition list */
    while (node != null) {
        Node next = node.next;
        node.next = null;
        if (node.data < x) {
            if (beforeStart == null) {
                beforeStart = node;
                beforeEnd = beforeStart;
            } else {
                beforeEnd.next = node;
                beforeEnd = beforeEnd.next;
            }
        } else {
            if (afterStart == null) {
                afterStart = node;
                afterEnd = afterStart;
            } else {
                afterEnd.next = node;
                afterEnd = afterEnd.next;
            }
        }
        node = next;    
    }

    /* Merge before list and after list */
    if (beforeStart == null) {
        return afterStart;
    }

    beforeEnd.next = afterStart;
    return beforeStart;
}

Upvotes: 0

Views: 982

Answers (2)

Matt Timmermans
Matt Timmermans

Reputation: 59303

The loop in your question removes nodes from the head of the original list, and appends them to the before list or the after list, until the original list is empty. Then it concatenates the before and after lists.

That's easy to explain and easy to understand.

It can be done without the temporary next or nulling out node.next in every iteration, but then the above description would no longer apply -- nodes would not be removed from the original list in every iteration, the before list and after list would not contain only the appropriate nodes, the operation you perform on them is not 'appending', and nodes would even appear in multiple lists for a while.

Your algorithm would suddenly be a lot more difficult to describe and understand. That is a bad thing in software development, and a bad thing in a coding interview.

Upvotes: 0

rcgldr
rcgldr

Reputation: 28921

Why can't I just do node = node.next at the end of the while loop?

It can be done this way. After doing the partition, for each list, you need to set the last node's next pointer to NULL. This will just take two lines of code.

The example code is using next = node.next and node.next = NULL to terminate each list during the partition process, but in this case that's not needed, since the lists don't need NULL terminators until after the partition process is done.

Upvotes: 2

Related Questions