LeetCode-148. Sort List

LeetCode-148. Sort List

Posted by Jae on September 3, 2019

1、题目

Sort a linked list in O(n log n) time using constant space complexity.

Example 1:

Input: 4->2->1->3 Output: 1->2->3->4 Example 2:

Input: -1->5->3->4->0 Output: -1->0->3->4->5

2、思路

这道题让我们在使用常量空间和nlgn的时间复杂度对单链表进行排序,在排序算法中时间复杂度能达到nlgn的有快速排序、归并排序和堆排序,,这里我们使用快速排序算法进行实现,快速排序的思想为:首先选一个枢轴,对于一趟排序过后,枢轴左边的元素都小于枢轴,枢轴右边的元素都大于枢轴,然后递归的对枢轴左半部分,右半部分进行排序,知道数组有序。

但是题目给的是单链表,只能从头节点往后遍历,所以我们把第一个节点作为枢轴,从前往后遍历,遇到比枢轴小的元素进行元素交换,遇到比枢轴大的元素跳过,例如 4->3->2->5->7->null 枢轴为4,定义指针p指向枢轴,q指向枢轴下一个元素,q指针往前遍历,遇到节点值小于枢轴4,则p=p.next,交换p和q节点的值,直到q节点指向链表尾null时,第一趟结束,此时交换p节点和枢轴的值,则p就是一次划分的分割点。

上面链表第一趟排序结果为:2->3->4->5->7->null

3 实现

public class Solution{
  public ListNode sortList(ListNode head) {
      return sortListHelper(head, null);
  }
  public ListNode sortListHelper(ListNode pHead, ListNode pTail){
      if (pHead != pTail){
          ListNode p = patition(pHead, pTail);
          sortListHelper(pHead, p);
          sortListHelper(p.next, pTail);
      }
      return pHead;
  }

  public ListNode patition(ListNode begin, ListNode end){
      int key = begin.val;
      ListNode p = begin;
      ListNode q = begin.next;
      while (q != end){
          if (q.val < key){
            // SWAP
            p = p.next;
            int t = p.val;
            p.val = q.val;
            q.val = t;
          }
          q = q.next;
      }
      begin.val = p.val;
      p.val = key;
      return p;
  }
}