单链表排序

单链表排序

问题

这个题目说的是，给你一个单链表，你要写一个函数，对它进行排序，然后返回排序后的链表。

比如说，给你的单链表是：

4 -> 8 -> 2 -> 1

你要返回排序后的链表：

1 -> 2 -> 4 -> 8

代码

public class AlgoCasts {

  public class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
      val = x;
    }
  }

  private void swap(ListNode a, ListNode b) {
    int tmp = a.val;
    a.val = b.val;
    b.val = tmp;
  }

  private void quickSort(ListNode head, ListNode end) {
    if (head == end || head.next == end) return;
    int pivot = head.val;
    ListNode slow = head, fast = head.next;
    while (fast != end) {
      if (fast.val <= pivot) {
        slow = slow.next;
        swap(slow, fast);
      }
      fast = fast.next;
    }
    swap(head, slow);
    quickSort(head, slow);
    quickSort(slow.next, end);
  }

  // Time: O(n*log(n)), Space: O(n)
  public ListNode quickSortList(ListNode head) {
    quickSort(head, null);
    return head;
  }

  private ListNode mergeTwoSortedLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0), 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;
  }

  // Time: O(n*log(n)), Space: O(log(n))
  public ListNode mergeSortList(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode fast = head, slow = head;
    while (fast.next != null && fast.next.next != null) {
      slow = slow.next;
      fast = fast.next.next;
    }
    ListNode right = mergeSortList(slow.next);
    slow.next = null;
    ListNode left = mergeSortList(head);
    return mergeTwoSortedLists(left, right);
  }

}