对链表进行插入排序
原题链接
假设一个dummy头结点插到head之前，后面进行模拟操作
代码如下：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode insertionSortList(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode curNode = head;
// curNode遍历整个链表
while (curNode != null && curNode.next != null) {
// 满足升序排列条件，不处理当前结点
if (curNode.val <= curNode.next.val) {
curNode = curNode.next;
continue;
}
// 跳出if后，下面就是要处理当前结点的下个结点的操作
ListNode temp = curNode.next;
curNode.next = curNode.next.next; // 保存完待删结点后就可以删除结点了
ListNode preNode = dummy;
// 找到temp应该插入到哪个位置
while (preNode.next.val <= temp.val) {
preNode = preNode.next;
}
// 接下来把temp插入到preNode和其next的中间
temp.next = preNode.next;
preNode.next = temp;
}
return dummy.next;
}
}
