创建节点类
public class Node {
int n;
Node next;
}
第1次推导
public class test {
public static void main(String[] args) {
// 新建节点
Node node1 = new Node();
node1.n = 9;
Node node2 = new Node();
node2.n = 6;
Node node3 = new Node();
node3.n = 2;
Node node4 = new Node();
node4.n = 5;
// 链接
Node head = new Node();
head.next = node1;
node1.next = node2;
node2.next = node3;
node3.next = node4;
// 长度
int len = 4;
// 遍历
Node node = head;
while (node.next != null) {
node = node.next;
int num = node.n;
System.out.print(num + ",");
}
Node top;
Node cur;
Node nex;
/**
* 初始为 9,6,2,5,
* 第1轮比较开始
*/
// top=head;
// cur=top.next;
// nex = cur.next;
// [head][9][6][2][5]
// [head][cur][nex][][]
cur=head;
top=cur;
for (int i = 0; i < 0; i++) { // 找top节点
top=top.next;
}
for (int i = 0; i < 1; i++) { // 找cur节点
cur=cur.next;
}
nex=cur.next;
if(cur.n>nex.n){
cur.next= nex.next;
top.next= nex;
nex.next=cur;
}
// 否则不做改变
// [head][6][9][2][5]
// [head][top][cur][nex][]
cur=head;
top=cur;
for (int i = 0; i < 1; i++) { // 找top节点
top=top.next;
}
for (int i = 0; i < 2; i++) { // 找cur节点
cur=cur.next;
}
nex=cur.next;
if(cur.n>nex.n){
cur.next= nex.next;
top.next= nex;
nex.next=cur;
}
// 否则不做改变
// [head][6][2][9][5]
// [head][][top][cur][nex]
cur=head;
top=cur;
for (int i = 0; i < 2; i++) { // 找top节点
top=top.next;
}
for (int i = 0; i < 3; i++) { // 找cur节点
cur=cur.next;
}
nex=cur.next;
if(cur.n>nex.n){
cur.next= nex.next;
top.next= nex;
nex.next=cur;
} // 6,2,5,9
// 否则不做改变
System.out.println();
// 遍历
Node cur1=head;
while (cur1.next != null){
cur1=cur1.next;
int num = cur1.n;
System.out.print(num + ",");
}
/**
* 第1轮结束为 6,2,5,9,
* 第2轮比较开始
*/
// [head][6][2][5][9]
// [head][cur][nex][][]
cur=head;
top=cur;
for (int i = 0; i < 0; i++) { // 找top节点
top=top.next;
}
for (int i = 0; i < 1; i++) { // 找cur节点
cur=cur.next;
}
nex=cur.next;
if(cur.n>nex.n){
cur.next= nex.next;
top.next= nex;
nex.next=cur;
}
// 否则不做改变
// [head][2][6][5][9]
// [head][top][cur][nex][]
cur=head;
top=cur;
for (int i = 0; i < 1; i++) { // 找top节点
top=top.next;
}
for (int i = 0; i < 2; i++) { // 找cur节点
cur=cur.next;
}
nex=cur.next;
if(cur.n>nex.n){
cur.next= nex.next;
top.next= nex;
nex.next=cur;
}
// 否则不做改变
System.out.println();
// 遍历
Node cur2=head;
while (cur2.next != null){
cur2=cur2.next;
int num = cur2.n;
System.out.print(num + ",");
} // 2,5,6,9,
/**
* 第2轮结束为 2,5,6,9,
* 第3轮比较开始
*/
// [head][2][5][6][9]
// [head][cur][nex][][]
cur=head;
top=cur;
for (int i = 0; i < 0; i++) { // 找top节点
top=top.next;
}
for (int i = 0; i < 1; i++) { // 找cur节点
cur=cur.next;
}
nex=cur.next;
if(cur.n>nex.n){
cur.next= nex.next;
top.next= nex;
nex.next=cur;
}
// 否则不做改变
System.out.println();
// 遍历
Node cur3=head;
while (cur3.next != null){
cur3=cur3.next;
int num = cur3.n;
System.out.print(num + ",");
} // 2,5,6,9,
}
}
最终完善
public class test {
public static void main(String[] args) {
// 新建节点
Node node1 = new Node();
node1.n = 9;
Node node2 = new Node();
node2.n = 6;
Node node3 = new Node();
node3.n = 2;
Node node4 = new Node();
node4.n = 5;
// 链接
Node head = new Node();
head.next = node1;
node1.next = node2;
node2.next = node3;
node3.next = node4;
// 长度
int len = 4;
System.out.println("--- 未排序 ---");
// 遍历
Node node = head;
while (node.next != null) {
node = node.next;
int num = node.n;
System.out.print(num + ",");
}
// 排序
// [head][9][6][2][5]
//[head][node1][node2][node3][node4]
Node top;
Node cur;
Node nex;
for(int b = len-1; b>0; b--){ // 3轮比较
int index=0;
for(int a = b; a>0; a--){
cur=head;
top=cur;
for (int i = 0; i < index; i++) { // 找top节点
top=top.next;
}
for (int i = 0; i < index+1; i++) { // 找cur节点
cur=cur.next;
}
nex=cur.next;
if(cur.n>nex.n){
cur.next= nex.next;
top.next= nex;
nex.next=cur;
}
index++;
}
}
System.out.println();
System.out.println("--- 排序后 ---");
// 遍历
Node cur1=head;
while (cur1.next != null){
cur1=cur1.next;
int num = cur1.n;
System.out.print(num + ",");
}
}
}
升序的情况下插入一条数据，链表依然为升序
public class test7 {
public static void main(String[] args) {
// 新建节点
Node node1 = new Node();
node1.n = 2;
Node node2 = new Node();
node2.n = 6;
Node node3 = new Node();
node3.n = 7;
Node node4 = new Node();
node4.n = 9;
// 链接
Node head = new Node();
head.next = node1;
node1.next = node2;
node2.next = node3;
node3.next = node4;
// 长度
int len = 4;
System.out.println("--- 初始链表 ---");
// 遍历
Node node = head;
while (node.next != null) {
node = node.next;
int num = node.n;
System.out.print(num + ",");
}
// 要插入的节点
Node node5 = new Node();
node5.n = 9;
// [head][2][6][7][9]
Node top;
Node cur;
for (int i = 0; i < len; i++) { // 比较len轮
// 每次找到要比较的节点和指定节点的前一个节点
cur=head;
top=cur;
for (int j = 0; j < i; j++) { // 找top节点
top=top.next;
}
for (int j = 0; j < i+1; j++) { // 找cur节点
cur=cur.next;
}
if (node5.n<cur.n){ // 在某本节点前时
// 插入位置
top.next=node5;
node5.next=cur;
// 长度++
len++;
// 结束整个循环
break;
}else { // 大于等于node1
// 不成立则continue，进入下一轮比较
continue;
}
}
Node end=head;
for(int j=0; j<len; j++){ // 找到最后
end=end.next;
}
// 当插入的值比数组中最大的值还大时，插入到最后
if(node5.n>=end.n){
end.next=node5;
len++;
}
System.out.println();
System.out.println("--- 链表插入节点后 ---");
// 遍历
Node cur1=head;
while (cur1.next != null){
cur1=cur1.next;
int num = cur1.n;
System.out.print(num + ",");
}
}
}
