链表排序 Sort List

2018-08-11 23:50:30

问题描述：

问题求解：

解法一、归并排序

    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode prev = null, slow = head, fast = head;
        while (fast != null && fast.next != null) {
            prev = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        prev.next = null;
        ListNode l1 = sortList(head);
        ListNode l2 = sortList(slow);
        return merge(l1, l2);
    }

    private ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode p = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                p.next = l1;
                l1 = l1.next;
            }
            else {
                p.next = l2;
                l2 = l2.next;
            }
            p = p.next;
        }
        if (l1 != null) {
            p.next = l1;
        }
        if (l2 != null) {
            p.next = l2;
        }
        return dummy.next;
    }

解法二、快速排序

  public ListNode sortList(ListNode head) {
    if (head == null || head.next == null)
      return head;  
    qsort(head, null);  
    return head;  
  }

    // [begin, end)
    void qsort(ListNode begin, ListNode end) {
        if (begin == end || begin.next == end) return;
        ListNode mid = partition(begin, end);
        qsort(begin, mid);
        qsort(mid.next, end);
    }

    ListNode partition(ListNode begin, ListNode end) {
        int key = begin.val;
        ListNode p = begin;
        ListNode q = begin.next;
        while (q != end) {
            if (q.val < key) {
                p = p.next;
                int tmp = p.val;
                p.val = q.val;
                q.val = tmp;
            }
            q = q.next;
        }
        int tmp = p.val;
        p.val = begin.val;
        begin.val = tmp;
        return p;
    }