|
| 1 | +/** |
| 2 | + * Definition for singly-linked list. |
| 3 | + * public class ListNode { |
| 4 | + * int val; |
| 5 | + * ListNode next; |
| 6 | + * ListNode() {} |
| 7 | + * ListNode(int val) { this.val = val; } |
| 8 | + * ListNode(int val, ListNode next) { this.val = val; this.next = next; } |
| 9 | + * } |
| 10 | + */ |
| 11 | +classSolution { |
| 12 | +// Merge Sort Implementation |
| 13 | +publicListNodegetMid(ListNodehead){ |
| 14 | +ListNodeslow=head,fast=head.next; |
| 15 | +while(fast !=null &&fast.next !=null){ |
| 16 | +fast =fast.next.next; |
| 17 | +slow =slow.next; |
| 18 | + } |
| 19 | +returnslow; |
| 20 | + } |
| 21 | +publicListNodemerge(ListNodeleft,ListNoderight){ |
| 22 | +ListNodedummy =newListNode(); |
| 23 | +ListNodetail =dummy; |
| 24 | + |
| 25 | +while(left !=null &&right !=null){ |
| 26 | +if(left.val <right.val){ |
| 27 | +tail.next =left; |
| 28 | +left =left.next; |
| 29 | + }else{ |
| 30 | +tail.next =right; |
| 31 | +right =right.next; |
| 32 | + } |
| 33 | +tail =tail.next; |
| 34 | + } |
| 35 | +if(left !=null){ |
| 36 | +tail.next =left; |
| 37 | + } |
| 38 | +if(right !=null){ |
| 39 | +tail.next =right; |
| 40 | + } |
| 41 | +returndummy.next; |
| 42 | + } |
| 43 | +publicListNodesortList(ListNodehead) { |
| 44 | +if(head ==null ||head.next ==null){ |
| 45 | +returnhead; |
| 46 | + } |
| 47 | + |
| 48 | +// Split the list in 2 halfs |
| 49 | +ListNodeleft =head; |
| 50 | +ListNoderight =getMid(head); |
| 51 | +ListNodetmp =right.next; |
| 52 | +right.next =null; |
| 53 | +right =tmp; |
| 54 | + |
| 55 | +left =sortList(left); |
| 56 | +right =sortList(right); |
| 57 | +returnmerge(left,right); |
| 58 | + } |
| 59 | +} |
| 60 | + |
| 61 | +// Using a Heap to sort the list |
1 | 62 | classSolution { |
2 | 63 | publicListNodesortList(ListNodehead) { |
3 | 64 | if(head ==null ||head.next ==null){ |
|