4
\$\begingroup\$

In this iteration, I incorporated all but one points made by forsvarir in the previous iteration. Now my code looks like this:

LinkedListNode.java:

package net.coderodde.fun;

/**
 * This class implements a node in a singly-linked list.
 *
 * @param <E> the type of the datum hold by this node.
 */
public class LinkedListNode<E> {

    private final E datum;
    private LinkedListNode<E> next;

    public LinkedListNode(final E datum) {
        this.datum = datum;
    }

    public E getDatum() {
        return datum;
    }

    public LinkedListNode<E> getNext() {
        return next;
    }

    public void setNext(final LinkedListNode<E> node) {
        this.next = node;
    }

    public static <E> String toString(LinkedListNode<E> head) {
        final StringBuilder sb = new StringBuilder().append('[');
        LinkedListNode<E> current = head;

        if (current != null) {
            sb.append(current.getDatum());
            current = current.getNext();
        }

        while (current != null) {
            sb.append(", ").append(current.getDatum());
            current = current.getNext();
        }

        return sb.append(']').toString();
    }
}

ListMergesort.java:

package net.coderodde.fun;

/**
 * This class contains a method for sorting a singly-linked list.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Jul 28, 2016)
 */
public class ListMergesort {

    private ListMergesort() {}

    public static <E extends Comparable<? super E>>
    LinkedListNode<E> mergesort(final LinkedListNode<E> head) {
        if (head == null || head.getNext() == null) {
            return head;
        }

        return mergesortImpl(head);
    }

    private static <E extends Comparable<? super E>>
    LinkedListNode<E> mergesortImpl(final LinkedListNode<E> head) {
        if (head.getNext() == null) {
            return head;
        }

        final LinkedListNode<E> leftSublistHead  = head;
        final LinkedListNode<E> rightSublistHead = head.getNext();

        LinkedListNode<E> leftSublistTail  = leftSublistHead;
        LinkedListNode<E> rightSublistTail = rightSublistHead;

        LinkedListNode<E> currentNode = rightSublistHead.getNext();
        boolean left = true;

        // Split the input linked list into two smaller linked lists:
        while (currentNode != null) {
            if (left) {
                leftSublistTail.setNext(currentNode);
                leftSublistTail = currentNode;
                left = false;
            } else {
                rightSublistTail.setNext(currentNode);
                rightSublistTail = currentNode;
                left = true;
            }

            currentNode = currentNode.getNext();
        }

        leftSublistTail.setNext(null);
        rightSublistTail.setNext(null);

        return merge(mergesortImpl(leftSublistHead),
                     mergesortImpl(rightSublistHead));
    }

    private static <E extends Comparable<? super E>>
    LinkedListNode<E> merge(LinkedListNode<E> leftSortedListHead,
                            LinkedListNode<E> rightSortedListHead) {
        LinkedListNode<E> mergedListHead;
        LinkedListNode<E> mergedListTail;

        if (rightSortedListHead.getDatum()
                               .compareTo(leftSortedListHead.getDatum()) < 0) {
            mergedListHead = rightSortedListHead;
            mergedListTail = rightSortedListHead;
            rightSortedListHead = rightSortedListHead.getNext();
        } else {
            mergedListHead = leftSortedListHead;
            mergedListTail = leftSortedListHead;
            leftSortedListHead  = leftSortedListHead.getNext();
        }

        while (leftSortedListHead != null && rightSortedListHead != null) {
            if (rightSortedListHead
                    .getDatum()
                    .compareTo(leftSortedListHead.getDatum()) < 0) {
                mergedListTail.setNext(rightSortedListHead);
                mergedListTail = rightSortedListHead;
                rightSortedListHead = rightSortedListHead.getNext();
            } else {
                mergedListTail.setNext(leftSortedListHead);
                mergedListTail = leftSortedListHead;
                leftSortedListHead = leftSortedListHead.getNext();
            }
        }

        if (leftSortedListHead != null) {
            mergedListTail.setNext(leftSortedListHead);
        } else {
            mergedListTail.setNext(rightSortedListHead);
        }

        return mergedListHead;
    }
}

Demo.java:

package net.coderodde.fun;

import java.util.Random;
import static net.coderodde.fun.ListMergesort.mergesort;

public class Demo {

    public static void main(final String[] args) {
        final long seed = System.nanoTime();
        final Random random = new Random(seed);
        LinkedListNode<Integer> head = createRandomLinkedList(10, random);
        System.out.println("Seed = " + seed);

        System.out.println(LinkedListNode.toString(head));
        head = mergesort(head);
        System.out.println(LinkedListNode.toString(head));
    }

    private static LinkedListNode<Integer> 
        createRandomLinkedList(final int size, final Random random) {
        if (size == 0) {
            return null;
        }

        LinkedListNode<Integer> head = new LinkedListNode<>(
                                           random.nextInt(100));
        LinkedListNode<Integer> tail = head;

        for (int i = 1; i < size; ++i) {
            final LinkedListNode<Integer> newnode = 
                    new LinkedListNode<>(random.nextInt(100));

            tail.setNext(newnode);
            tail = newnode;
        }

        return head;
    }
}

As always, any critique is much appreciated.

\$\endgroup\$
3
\$\begingroup\$

I think, toString() in LinkedListNode.java could be refactored. Let's just keep things simpler. (^_-)

  • I thought at runtime, whether the current(parameter that pass-in) is null or not, it always have to check 2 conditions always. We can actually write it with a single if(current != null) checking.

  • While loop will run as long as it has a next element. (Adopted this style from usual BufferedReader file reading)

  • No need of extra local variable to be created. We can get rid of it.

     public static <E> String toString(LinkedListNode<E> current) {
        final StringBuilder sb = new StringBuilder().append('[');
    
        if (current != null) {
            sb.append(current.getDatum());
    
            while ((current = current.getNext()) != null) {
                sb.append(", ").append(current.getDatum());
            }
        }
    
        return sb.append(']').toString();
    }
    
\$\endgroup\$
5
  • 4
    \$\begingroup\$ This rewrite could potentially cause performance issues now that the StringBuilder is gone \$\endgroup\$ – Pimgd Jul 29 '16 at 13:09
  • 2
    \$\begingroup\$ ... and a good old stack overflow. (^_-) \$\endgroup\$ – coderodde Jul 29 '16 at 13:11
  • \$\begingroup\$ The new rewrite looks a tad better, but I wouldn't call it simpler. ... You're also not really explaining the changes made and as a result it looks like a code dump. If you could explain what changes you have made and why you have made these changes then this answer could be good. \$\endgroup\$ – Pimgd Aug 1 '16 at 8:19
  • \$\begingroup\$ That looks nice! \$\endgroup\$ – coderodde Aug 2 '16 at 15:57
  • \$\begingroup\$ All of your comments and pin points inspired me to somehow improve that method. So made it. :) \$\endgroup\$ – Jude Niroshan Aug 2 '16 at 17:34
4
\$\begingroup\$
if (left) {
    leftSublistTail.setNext(currentNode);
    leftSublistTail = currentNode;
    left = false;
} else {
    rightSublistTail.setNext(currentNode);
    rightSublistTail = currentNode;
    left = true;
}

Looks like we can simplify this a teeny-tiny bit by inverting left rather than manually setting it.

if (left) {
    leftSublistTail.setNext(currentNode);
    leftSublistTail = currentNode;
} else {
    rightSublistTail.setNext(currentNode);
    rightSublistTail = currentNode;
}
left = !left;

It seems this was already pointed out to you, but still, I would say that this is a positive change - it's a simplification and the old situation doesn't make more sense from a semantic view point. It really is "and now, the next item needs to go in the other list" rather than "if we added the item to the left list, it now needs to go in the right list, and if we added the item to the right list, it now needs to go in the left list".

\$\endgroup\$
3
  • \$\begingroup\$ I guess that answers the what point wasn't implemented question :) \$\endgroup\$ – forsvarir Jul 29 '16 at 13:34
  • \$\begingroup\$ @forsvarir Sorry, I didn't read the previous question =D \$\endgroup\$ – Pimgd Jul 29 '16 at 13:35
  • 4
    \$\begingroup\$ No problem, I find it hard not to agree with myself \$\endgroup\$ – forsvarir Jul 29 '16 at 13:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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