合并排序链接列表

Question

我最近重新整理了一些基本知识，发现合并对链表进行排序是一个非常好的挑战。如果您有一个好的实现，那么请在此处展示它。

Answer 1

想知道为什么它应该是这里所说的巨大挑战，这是Java中没有任何“聪明把戏”的简单实现。//The main functionpublic static Node merge_sort(Node head)&nbsp;{&nbsp; &nbsp; if(head == null || head.next == null)&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; return head;&nbsp; &nbsp; Node middle = getMiddle(head);&nbsp; &nbsp; &nbsp; //get the middle of the list&nbsp; &nbsp; Node left_head = head;&nbsp; &nbsp; Node right_head = middle.next;&nbsp;&nbsp; &nbsp; middle.next = null;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;//split the list into two halfs&nbsp; &nbsp; return merge(merge_sort(left_head), merge_sort(right_head));&nbsp; //recurse on that}//Merge subroutine to merge two sorted listspublic static Node merge(Node a, Node b){&nbsp; &nbsp; Node dummyHead = new Node();&nbsp; &nbsp; for(Node current&nbsp; = dummyHead; a != null && b != null; current = current.next;)&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; if(a.data <= b.data)&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; current.next = a;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; a = a.next;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; else&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; current.next = b;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; b = b.next;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; current.next = (a == null) ? b : a;&nbsp; &nbsp; return dummyHead.next;}//Finding the middle element of the list for splittingpublic static Node getMiddle(Node head){&nbsp; &nbsp; if(head == null)&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; return head;&nbsp; &nbsp; Node slow = head, fast = head;&nbsp; &nbsp; while(fast.next != null && fast.next.next != null)&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; slow = slow.next;&nbsp; &nbsp; &nbsp; &nbsp; fast = fast.next.next;&nbsp; &nbsp; }&nbsp; &nbsp; return slow;}