题解 | JAVA 快排#单链表的排序 [P3]

看大部分解体都是用的mergeSort, 所以就写个quickSort的版本.

就是最普通的QuickSort只不过把数字换成Node存到一个Array里

时间: O(nlogn)
空间: O(n)

import java.util.*;

public class Solution {
    public ListNode sortInList (ListNode head) {
      if (head == null) return null;

      List<ListNode> arr = new ArrayList<>();
      while (head != null) {
        arr.add(head);
        head = head.next;
      }
      
      quickSort(arr, 0, arr.size() - 1);

      // reconstruct list from sorted array of ListNodes.
      ListNode sentinal = new ListNode(-1); // dummy
      ListNode curLast = sentinal;
      for (ListNode n : arr) {
        curLast.next = n;
        curLast = curLast.next;
      }
      curLast.next = null;  // !!important, otherwise will form loop
      return sentinal.next;
    }
  
    void quickSort(List<ListNode> arr, int start, int end) {
      if (start >= end) return;
      int pivot = partition(arr, start, end);
      quickSort(arr, start, pivot-1);
      quickSort(arr, pivot+1, end);
    }
  
    int partition(List<ListNode> arr, int start, int end) {
      int pivVal = arr.get(start).val;
      int i = start, j = end;
      while (i < j) {
        while (i < end && arr.get(i).val <= pivVal) i++;
        while (j > start && arr.get(j).val >= pivVal) j--;
        if (i < j) swapNode(arr, i, j);
      }
      swapNode(arr, start, j);
      return j;
    }
  
    void swapNode(List<ListNode> arr, int i, int j) {
      ListNode tmp = arr.get(i);
      arr.set(i, arr.get(j));
      arr.set(j, tmp);
    }
}