https://leetcode-cn.com/problems/sort-list/
-
自顶向下归并排序
对链表自顶向下归并排序的过程如下。
找到链表的中点，以中点为分界，将链表拆分成两个子链表。寻找链表的中点可以使用快慢指针的做法，快指针每次移动 22 步，慢指针每次移动 11 步，当快指针到达链表末尾时，慢指针指向的链表节点即为链表的中点。
对两个子链表分别排序。
将两个排序后的子链表合并，得到完整的排序后的链表。可以使用「21. 合并两个有序链表」的做法，将两个有序的子链表进行合并。
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode sortList(ListNode head) { if(head==null||head.next==null){ return head; } ListNode slow = head; ListNode fast = head.next; while (fast!=null&&fast.next!=null){ slow = slow.next; fast = fast.next.next; } ListNode head2 = slow.next; slow.next=null; return merge(sortList(head),sortList(head2)); } private ListNode merge(ListNode head1, ListNode head2) { ListNode ans = new ListNode(0); ListNode temp1 = head1,temp2 = head2,temp = ans; while (temp1!=null&&temp2!=null){ if(temp1.val<temp2.val){ temp.next = temp1; temp1 = temp1.next; }else{ temp.next = temp2; temp2 = temp2.next; } temp=temp.next; } if(temp1!=null){ temp.next=temp1; }else if(temp2!=null){ temp.next=temp2; } return ans.next; } }
