解法:归并排序
归并排序需要将链表分成长度均等的左右两部分,分别对两部分进行排序之后再合并
如何把两个链表分成长度均等的两部分? 快慢指针
import java.util.*; public class Solution { /** * * @param head ListNode类 the head node * @return ListNode类 */ public ListNode sortInList (ListNode head) { if (head == null || head.next == null) { return head; } // only 2 nodes if (head.next.next == null) { if (head.next.val < head.val) { int temporary = head.next.val; head.next.val = head.val; head.val = temporary; } return head; } // find middle ListNode slow = head; ListNode fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } ListNode middle = slow.next; // break down linked list into two part slow.next = null; return merge(sortInList(head), sortInList(middle)); } private ListNode merge(ListNode head1, ListNode head2) { if (head1 == null) { return head2; } if (head2 == null) { return head1; } ListNode previousOfHead = new ListNode(-1000000001); ListNode current = previousOfHead; while (head1 != null && head2 != null) { if (head1.val <= head2.val) { current.next = head1; head1 = head1.next; } else { current.next = head2; head2 = head2.next; } current = current.next; } if (head1 != null) { current.next = head1; } else { current.next = head2; } return previousOfHead.next; } }