class Node{
Node next;
int data;
Node(){}
Node(int data){
this.data=data;
}
}
class NodeTest{
static int[] sz={5,4,3,2,1};
//生成一个含有5个节点的单链表。
public Node makList(){
Node head=new Node();
Node tem=head;
for(int i=0;i<sz.length;i++){
Node node=new Node(sz[i]);
tem.next=node;
tem=tem.next;
}
return head;
}
//打印单链表。
public void ShowList(Node head){
Node temp=head.next;
while(temp!=null){
System.out.print(temp.data+" ");
temp=temp.next;
}
System.out.println();
}
//为了标记次数,每排序依次,int c加1,c的值在主方法的for循环中增加。
public void ShowList2(Node head,int c){
Node temp=head.next;
while(temp!=null){
System.out.print(temp.data+" ");
temp=temp.next;
}
System.out.print("第 "+c+" 次");
System.out.println();
}
/*这个sort2方法是无意中写的,只增加了一个tem指针,在执行的时候,出现了一些情况:
*最开始单链表的节点数是5个,顺序是5,4,3,2,1主要是为了方便观察,通过24次遍历
*得到1,2,3,4,5。于是开始改变节点个数。
*2个节点(2,1):遍历1次。(第3 、5 、7 、9次也可以)
*3个节点(3,2,1):遍历4次。(第4 、8 、12 、16次也可以)
*4个节点(4,3,2,1):遍历9次。(第9 、17 、25 、33次也可以)
*5个节点(5,4,3,2,1):遍历24次。(第30 、36 、42 、48次也可以)
*6个节点(6,5,4,3,2,1):遍历25次。(第37 、49 、61 、73次也可以)
*7个节点(7,6,5,4,3,2,1):遍历多少次都无法实现1,2,3,4,5,6,7的结果。
*7个节点以后的无论几个节点,都无法实现反向排序。
*想知道大于7个节点的单链表为啥就不能实现反向排序呢?
**/
public void sort2(Node head){
Node pre=head;
Node cur=pre.next;
Node tem=cur.next;
while(tem!=null){
if(pre.data<cur.data){
pre.next=cur.next;
cur.next=tem.next;
tem.next=cur;
pre=tem;
tem=cur.next;
}else{
pre=cur;
cur=tem;
tem=tem.next;
}
}
}
public static void main (String[] args) {
NodeTest nt=new NodeTest();
Node head=nt.makList();//生成链表,返回头结点。
int c=1;
nt.ShowList(head);//打印单链表。
System.out.println("修改后");
for(int i=0;i<80;i++){//int i的大小自己定义,主要是为了便于观察。
nt.sort2(head);
nt.ShowList2(head,c);//打印改变后的单链表,并标记第几次遍历。
c++;
}
}
}