Java实现单链表排序

今天复习数据结构，想用单链表实现插入排序，在网上查资料，发现大部分都需要新建一个链表进行插入，感觉空间复杂度过高，便借用单链表原地反转的思想。

// 插入排序

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;

}

}

}