题解 | #单链表的排序#
单链表的排序
https://www.nowcoder.com/practice/f23604257af94d939848729b1a5cda08
相当于就是使用选择排序的，有几个关键点，1、就是使用一个dummy节点来记录每轮最小的元素，2、每次选择出一个最小的元素，然后将这个元素在head链表中剔除，这一步是必须要做的，不然排序就永远不可以结束，而且这样也可以减少排序的复杂度，3、注意删除已选中的节点时，需要保存两个信息：当前遍历节点的前置节点、已选中节点的前置节点，这样才能保证删除的正确性，4、需要注意几个细节：可能存在head节点就是最小的节点，所以在判断时需要预先判断一下是否和当前head一致，如果一致需要将head后推一个节点
public ListNode sortInList(ListNode head) {
ListNode dummy = new ListNode(-1), curd = dummy;
while (head != null) {
ListNode curSmallest = findSmallestNode(head);
if (curSmallest == null) {
return dummy.next;
}
if (curSmallest.equals(head)) {
head = head.next;
}
curd.next = curSmallest;
curd = curd.next;
}
return dummy.next;
}
private ListNode findSmallestNode(ListNode head) {
ListNode sm = head, headPre = null, smPre = null;
while (head != null) {
if (sm.val > head.val) {
smPre = headPre;
sm = head;
}
headPre = head;
head = head.next;
}
if (smPre != null) {
smPre.next = sm.next;
sm.next = null;
}
return sm;
}
