Advertisement
Guest User

Untitled

a guest
Jul 28th, 2016
51
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.38 KB | None | 0 0
  1. package net.coderodde.fun;
  2.  
  3. import java.util.Random;
  4.  
  5. /**
  6. * This class contains a method for sorting a singly-linked list.
  7. *
  8. * @author Rodion "rodde" Efremov
  9. * @version 1.6 (Jul 28, 2016)
  10. */
  11. public class ListMergesort {
  12.  
  13. /**
  14. * This class implements a node in a singly-linked list.
  15. *
  16. * @param <E> the type of the datum hold by this node.
  17. */
  18. public static final class LinkedListNode<E> {
  19.  
  20. private final E datum;
  21. private LinkedListNode<E> next;
  22.  
  23. public LinkedListNode(final E datum) {
  24. this.datum = datum;
  25. }
  26.  
  27. public E getDatum() {
  28. return datum;
  29. }
  30.  
  31. public LinkedListNode<E> getNext() {
  32. return next;
  33. }
  34.  
  35. public void setNext(final LinkedListNode<E> node) {
  36. this.next = node;
  37. }
  38. }
  39.  
  40. public static <E extends Comparable<? super E>>
  41. LinkedListNode<E> mergesort(final LinkedListNode<E> head) {
  42. if (head == null || head.getNext() == null) {
  43. return head;
  44. }
  45.  
  46. return mergesortImpl(head);
  47. }
  48.  
  49. private static <E extends Comparable<? super E>>
  50. LinkedListNode<E> mergesortImpl(final LinkedListNode<E> head) {
  51. if (head.getNext() == null) {
  52. return head;
  53. }
  54.  
  55. final LinkedListNode<E> leftSublistHead = head;
  56. final LinkedListNode<E> rightSublistHead = head.getNext();
  57.  
  58. LinkedListNode<E> leftSublistTail = leftSublistHead;
  59. LinkedListNode<E> rightSublistTail = rightSublistHead;
  60.  
  61. LinkedListNode<E> currentNode = rightSublistHead.getNext();
  62. boolean left = true;
  63.  
  64. // Split the input linked list into two smaller linked lists:
  65. while (currentNode != null) {
  66. if (left) {
  67. leftSublistTail.setNext(currentNode);
  68. leftSublistTail = currentNode;
  69. left = false;
  70. } else {
  71. rightSublistTail.setNext(currentNode);
  72. rightSublistTail = currentNode;
  73. left = true;
  74. }
  75.  
  76. currentNode = currentNode.getNext();
  77. }
  78.  
  79. leftSublistTail.setNext(null);
  80. rightSublistTail.setNext(null);
  81.  
  82. return merge(mergesortImpl(leftSublistHead),
  83. mergesortImpl(rightSublistHead));
  84. }
  85.  
  86. private static <E extends Comparable<? super E>>
  87. LinkedListNode<E> merge(LinkedListNode<E> leftSortedListHead,
  88. LinkedListNode<E> rightSortedListHead) {
  89. LinkedListNode<E> mergedListHead;
  90. LinkedListNode<E> mergedListTail;
  91.  
  92. if (rightSortedListHead.getDatum()
  93. .compareTo(leftSortedListHead.getDatum()) < 0) {
  94. mergedListHead = rightSortedListHead;
  95. mergedListTail = rightSortedListHead;
  96. rightSortedListHead = rightSortedListHead.getNext();
  97. } else {
  98. mergedListHead = leftSortedListHead;
  99. mergedListTail = leftSortedListHead;
  100. leftSortedListHead = leftSortedListHead.getNext();
  101. }
  102.  
  103. while (leftSortedListHead != null && rightSortedListHead != null) {
  104. if (rightSortedListHead
  105. .getDatum()
  106. .compareTo(leftSortedListHead.getDatum()) < 0) {
  107. mergedListTail.setNext(rightSortedListHead);
  108. mergedListTail = rightSortedListHead;
  109. rightSortedListHead = rightSortedListHead.getNext();
  110. } else {
  111. mergedListTail.setNext(leftSortedListHead);
  112. mergedListTail = leftSortedListHead;
  113. leftSortedListHead = leftSortedListHead.getNext();
  114. }
  115. }
  116.  
  117. while (leftSortedListHead != null) {
  118. mergedListTail.setNext(leftSortedListHead);
  119. mergedListTail = leftSortedListHead;
  120. leftSortedListHead = leftSortedListHead.getNext();
  121. }
  122.  
  123. while (rightSortedListHead != null) {
  124. mergedListTail.setNext(rightSortedListHead);
  125. mergedListTail = rightSortedListHead;
  126. rightSortedListHead = rightSortedListHead.getNext();
  127. }
  128.  
  129. mergedListTail.setNext(null);
  130. return mergedListHead;
  131. }
  132.  
  133. public static <E> String toString(LinkedListNode<E> head) {
  134. final StringBuilder sb = new StringBuilder();
  135.  
  136. while (head != null) {
  137. sb.append(head.getDatum()).append(' ');
  138. head = head.getNext();
  139. }
  140.  
  141. return sb.toString();
  142. }
  143.  
  144. private static LinkedListNode<Integer>
  145. createRandomLinkedList(final int size, final Random random) {
  146. if (size == 0) {
  147. return null;
  148. }
  149.  
  150. LinkedListNode<Integer> head = new LinkedListNode<>(
  151. random.nextInt(100));
  152. LinkedListNode<Integer> tail = head;
  153.  
  154. for (int i = 1; i < size; ++i) {
  155. final LinkedListNode<Integer> newnode =
  156. new LinkedListNode<>(random.nextInt(100));
  157.  
  158. tail.setNext(newnode);
  159. tail = newnode;
  160. }
  161.  
  162. return head;
  163. }
  164.  
  165. public static void main(final String... args) {
  166. final long seed = System.nanoTime();
  167. final Random random = new Random(seed);
  168. LinkedListNode<Integer> head = createRandomLinkedList(10, random);
  169. System.out.println("Seed = " + seed);
  170.  
  171. System.out.println(toString(head));
  172. head = mergesort(head);
  173. System.out.println(toString(head));
  174. }
  175. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement