Merge sorting a singly-linked list in Java - follow-up

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.

Replay

Category: java Time: 2016-07-29 Views: 0

Related post

iOS development

Android development

Python development

JAVA development

Development language

PHP development

Ruby development

search

Front-end development

Database

development tools

Open Platform

Javascript development

.NET development

cloud computing

server

Copyright (C) avrocks.com, All Rights Reserved.

processed in 0.132 (s). 12 q(s)