主要确定的步骤:
- 需要双重遍历。
- 对于待插入的结点小于首结点情况,做处理
- 找到对应插入的结点,进行插入。
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
*
* @param head ListNode类
* @return ListNode类
*/
public ListNode insertionSortList (ListNode head) {
// write code here
// write code here
if (head == null || head.next == null) {
return head;
}
// 永远标记未排序的首个结点
ListNode pB = head.next;
// 将原来的head摘干净
head.next = null;
// 便利已排序结点的指针
ListNode pA;
ListNode tmp;
while (pB != null) {
// 每次从头开始
pA = head;
// 处理头结点排序情况
if (pB.val < pA.val) {
tmp = pB.next;
// 这里是pA本身
pB.next = pA;
head = pB;
pB = tmp;
} else {
// 这里使用的是pA的next结点
while (pA.next != null && pA.next.val < pB.val) {
pA = pA.next;
}
tmp = pB.next;
pB.next = pA.next;
pA.next = pB;
pB = tmp;
}
}
return head;
}
}