今天复习数据结构，想用单链表实现插入排序，在网上查资料，发现大部分都需要新建一个链表进行插入，感觉空间复杂度过高，便借用单链表原地反转的思想。
// 插入排序
public void insertSortNode() {
if (Length() < 2) {
System.out.println("无需排序");
return;
}
Node temp = head;
Node pNode = head.next.next;
Node qNode = pNode.next;
temp.next.next = null;
while (qNode != null) {
pNode.next = null;
while (temp.next != null) {
if ((int) pNode.data < (int) temp.next.data) {
pNode.next = temp.next;
temp.next = pNode;
pNode = qNode;
qNode = qNode.next;
print();
break;
}
temp = temp.next;
}
if (temp.next == null) {
temp.next = pNode;
pNode = qNode;
qNode = qNode.next;
}
}
if (qNode == null) {
pNode.next = null;
while (temp.next != null) {
if ((int) pNode.data < (int) temp.next.data) {
pNode.next = temp.next;
temp.next = pNode;
print();
break;
}
temp = temp.next;
}
if (temp.next == null) {
temp.next = pNode;
}
}
}
