题目

image.png

思路

  • 由于要实现O(nlogn)的时间复杂度，所以需要使用归并排序来进行排序，归并排序的每次找到链表的中点，将链表切割成两段，直到长度为1，此时在合并每段代码

    代码

    1.   public ListNode sortList(ListNode head) {
    2.       if (head == null || head.next == null) return head;
    3.       return mergeSort(head);
    4.   }
    6.   public ListNode mergeSort(ListNode head) {
    7.       if (head.next == null) return head;
    8.       ListNode fast = head.next, slow = head;
    9.       while (fast != null && fast.next != null) {
    10.           fast = fast.next.next;
    11.           slow = slow.next;
    12.       }
    13.       fast = slow.next;
    14.       slow.next = null;
    15.       return merge(mergeSort(head), mergeSort(fast));
    16.   }
    18.   public ListNode merge(ListNode p1, ListNode p2) {
    19.       ListNode dummy = new ListNode(0);
    20.       ListNode p = dummy;
    21.       while (p1 != null && p2 != null) {
    22.           if (p1.val < p2.val) {
    23.               p.next = p1;
    24.               p1 = p1.next;
    25.           } else {
    26.               p.next = p2;
    27.               p2 = p2.next;
    28.           }
    29.           p = p.next;
    30.       }
    31.       p.next = p1 == null ? p2 : p1;
    32.       return dummy.next;
    33.   }

    排序链表