本文共 1972 字，大约阅读时间需要 6 分钟。

链接：

大意：

给定一个链表头结点head，要求使用时间复杂度O(nlogn)，空间复杂度O(1)的方法对链表节点进行排序，并返回新链表的头节点。例子：

思路：

上一题  。规定了只能用插入排序，但是为了提升效率，之后也是使用了快排和归并排序做对比。经过上一题的洗礼，知道了链表归并排序使用递归解决很方便，于是自己手写了归并排序（递归）。

代码：

// 时间复杂度O(nlogn) 空间复杂度O(1) 可以用归并排序了class Solution {    public ListNode sortList(ListNode head) {        if (head == null || head.next == null)            return head;        // 使用快慢指针找到链表中间元素        ListNode slow = head, fast = head;        while (fast.next != null && fast.next.next != null) {            slow = slow.next;            fast = fast.next.next;        }        ListNode l2 = slow.next;        slow.next = null; // 断链        // 分治        ListNode l = sortList(head);        ListNode r = sortList(l2);        return merge(l, r);    }    // 对两个有序链表使用递归进行排序    public 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;        }    }}

 结果：

结论：

无论使用递归还是迭代方式进行归并排序，分治都是必不可少的。另外：链表使用递归式归并排序确实很方便

最佳：

class Solution {	public ListNode sortList(ListNode head) {		if (head == null)			return null;		ListNode pivot = head;		head = head.next;		pivot.next = null;		if (head == null)			return pivot;		ListNode small = new ListNode(0);		ListNode large = new ListNode(0);		ListNode p = pivot;		ListNode s = small;		ListNode l = large;		while (head != null) {			if (head.val < pivot.val) {				s.next = head;				s = s.next;			} else if (head.val == pivot.val) {				p.next = head;				p = p.next;			} else {				l.next = head;				l = l.next;			}			head = head.next;		}		l.next = null;		s.next = null;		p.next = null;		ListNode ss = sortList(small.next);		if (ss == null) {			ss = pivot;		} else {			ListNode sss = ss;			while (sss.next != null) {				sss = sss.next;			}			sss.next = pivot;		}		p.next = sortList(large.next);		return ss;	}}

直接对链表使用快排，学到了学到了。 

转载地址：http://oxesi.baihongyu.com/