题目

输入一个链表的头节点，请将该链表排序。

分析

归并排序的主要思想是将链表分成两个子链表，在对两个子链表排序后再将它们合并成一个排序的链表。
这里可以用快慢双指针的思路将链表分成两半。如果慢指针一次走一步，快指针一次走两步，当快指针走到链表尾部时，慢指针只走到链表的中央，这样也就找到了链表后半部分的头节点。

解

public class Test {public static void main(String[] args) {ListNode listNode1 = new ListNode(1);ListNode listNode2 = new ListNode(2);ListNode listNode3 = new ListNode(3);ListNode listNode4 = new ListNode(4);ListNode listNode5 = new ListNode(5);ListNode listNode6 = new ListNode(6);listNode3.next = listNode5;listNode5.next = listNode1;listNode1.next = listNode4;listNode4.next = listNode2;listNode2.next = listNode6;ListNode result = sortList(listNode3);while (result != null) {System.out.println(result.val);result = result.next;}}public static ListNode sortList(ListNode head) {if (head == null || head.next == null) {return head;}ListNode head1 = head;ListNode head2 = split(head);head1 = sortList(head1);head2 = sortList(head2);return merge(head1, head2);}private static ListNode split(ListNode head) {ListNode slow = head;ListNode fast = head.next;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;}ListNode second = slow.next;slow.next = null;return second;}private static ListNode merge(ListNode head1, ListNode head2) {ListNode dummy = new ListNode(0);ListNode cur = dummy;while (head1 != null && head2 != null) {if (head1.val < head2.val) {cur.next = head1;head1 = head1.next;}else {cur.next = head2;head2 = head2.next;}cur = cur.next;}cur.next = head1 == null ? head2 : head1;return dummy.next;}
}