Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package net.coderodde.fun;
- import java.util.Random;
- /**
- * This class contains a method for sorting a singly-linked list.
- *
- * @author Rodion "rodde" Efremov
- * @version 1.6 (Jul 28, 2016)
- */
- public class ListMergesort {
- /**
- * This class implements a node in a singly-linked list.
- *
- * @param <E> the type of the datum hold by this node.
- */
- public static final 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 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();
- }
- }
- while (leftSortedListHead != null) {
- mergedListTail.setNext(leftSortedListHead);
- mergedListTail = leftSortedListHead;
- leftSortedListHead = leftSortedListHead.getNext();
- }
- while (rightSortedListHead != null) {
- mergedListTail.setNext(rightSortedListHead);
- mergedListTail = rightSortedListHead;
- rightSortedListHead = rightSortedListHead.getNext();
- }
- mergedListTail.setNext(null);
- return mergedListHead;
- }
- public static <E> String toString(LinkedListNode<E> head) {
- final StringBuilder sb = new StringBuilder();
- while (head != null) {
- sb.append(head.getDatum()).append(' ');
- head = head.getNext();
- }
- return sb.toString();
- }
- 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;
- }
- 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(toString(head));
- head = mergesort(head);
- System.out.println(toString(head));
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement