领扣LintCode算法问题答案-98. 链表排序
目录
98. 链表排序描述样例 1：样例 2：
题解鸣谢
98. 链表排序
描述
在 O(n log n) 时间复杂度和常数级的空间复杂度下给链表排序。
样例 1：
输入: 1->3->2->null
输出: 1->2->3->null
样例 2：
输入: 1->7->2->6->null
输出: 1->2->6->7->null
题解
public class Solution {
public ListNode
sortList(ListNode head
) {
quickSort(head
, null
);
return head
;
}
private void quickSort(ListNode head
, ListNode tail
) {
if (head
== tail
) {
return;
}
ListNode pt
= partition(head
, tail
);
quickSort(head
, pt
);
quickSort(pt
.next
, tail
);
}
private ListNode
partition(ListNode head
, ListNode tail
) {
int pivot
= head
.val
;
ListNode p1
= head
;
ListNode p2
= head
.next
;
while (p2
!= tail
) {
if (p2
.val
< pivot
) {
p1
= p1
.next
;
swap(p1
, p2
);
}
p2
= p2
.next
;
}
swap(head
, p1
);
return p1
;
}
private void swap(ListNode n1
, ListNode n2
) {
if (n1
!= n2
) {
int tmp
= n1
.val
;
n1
.val
= n2
.val
;
n2
.val
= tmp
;
}
}
}
原题链接点这里
鸣谢
非常感谢你愿意花时间阅读本文章，本人水平有限，如果有什么说的不对的地方，请指正。 欢迎各位留言讨论，希望小伙伴们都能每天进步一点点。
