148.Sort-List

148. Sort List

题目地址

https://www.lintcode.com/problem/sort-list/

https://leetcode.com/problems/sort-list/

题目描述

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

代码

Approach #1 Divide and Conquer

public class Solution {
    public ListNode sortList (ListNode head) {
    if (head == null | head.next == null) return head;

    ListNode mid = findMid(head);
    ListNode head1 = head;
    ListNode head2 = mid.next;
    mid.next = null; //
    ListNode left = sortList(head1);
    ListNode right = sortList(head2);
    return merge(left, right);
  }

  public ListNode findMid(ListNode head){
    if (head == null) return null;
    ListNode slow = head;
    ListNode fast = head.next;
    while (fast != null && fast.next != null) {
      fast = fast.next.next;
      slow = slow.next;
    }
    return slow;
  }

  public ListNode merge(ListNode head1, ListNode head2) {
    ListNode dummy = new ListNode(0);
    ListNode head = dummy;
    while (head1 != null || head2 != null) {
      int a = head1 == null ? Integer.MAX_VALUE : head1.val;
      int b = head2 == null ? Integer.MAX_VALUE : head2.val;
      if (a < b) {
        head.next = new ListNode(a);
        if (head1 != null) head1 = head1.next;
      } else {
        head.next = new ListNode(b);
        if (head2 != null) head2 = head2.next;
      }
      head = head.next;
    }

    return dummy.next;
  }
}