教育改变生活

标题: leetcode真题-排序 [打印本页]

作者: 一秉 时间: 2020-8-3 16:21
标题: leetcode真题-排序
一、题目描述
在O(n log n)的时间内使用常数级空间复杂度对链表进行排序。
Sort a linked list in O(n log n) time using constant space complexity.
示例1
输入
{3,2,4}
输出
{2,3,4}
二、代码实现（Java）
public class Solution {
/**
   *
   * @param head ListNode类
   * @return ListNode类
   */
public ListNode sortList (ListNode head) {
      // write code here
      if (head == null || head.next == null) return head;
      ListNode mid = findMid(head);
      ListNode right = sortList(mid.next);
      mid.next = null;
      ListNode left = sortList(head);
      return merge(left,right);
}

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

ListNode merge(ListNode l1, ListNode l2) {
      if (l1== null) return l2;
      if (l2 == null) return l1;
      if (l1.val < l2.val) {
         l1.next = merge(l1.next, l2);
         return l1;
      } else {
         l2.next = merge(l1, l2.next);
         return l2;
      }
}
}

欢迎光临教育改变生活 (http://bbs.goldoar.com/)