Java 反转带头结点的单链表并显示输出的实现过程

Java 反转带头结点的单链表并显示输出的实现过程

注意：要保证已经有Node类和单链表的初始化，这样才能调用反转方法并显示结果。

方法如下：

//Node指泛型结点类

public void reverse2(Node head){

Node p=head.next;

Node q=head.next.next;

heabAZKaPKppad.next=null;

p.next=null;

while(q!=null){

Node temp=q.next;

q.next=p;

p=q;

q=temp;

}

q=this.head;

q.next=p;

/*

//想要直接在方法中遍历输出可以使用这段代码 ***p是反转后的第一个结点***

for(Node qq=p;qq!=null;qq=qq.next){//qq不能为q，因为结束循环后，p是最后一个结点，q是null

System.out.print(qq.data+"\t");

}

*/

}

实现过程如图所示：

在循环之前，先把head以及初始p的next断掉，方便后面的循环；循环中的q.next=p就是重定向，这一步把原来的next指向p；

不用q=q.next来使q向后移动，因为q结点的指针重指向后，q的next为空了，无法正确指向下一个结点。这时用temp结点来做一下过渡，在q指针重指向之前，把q的下一个结点赋给temp，即temp=q.next，在重指向后，用q=temp来向后移动；

p=q；q=temp就是往后移动一个结点，可以继续重复循环。

循环结束时，q为空，p为最后一个结点，使q作为头结点并指向p就完成了反转。

整体代码：

Node类：

public class Node{

public T data;

public Nodenext;

public Node(T data,Nodenext){

this.data=data;

this.next=next;

}

public Node(){

this(null,null);

}

public String toString(){

return this.data.toString();

}

}

单链表类：

public class SinglyList {

public Node head;

public SinglyList(){

this.head=new Node();

}

public SinglyList(T[] values){

this();

Node rear=this.head;

for(int i=0;i

{

rear.next=new Node(values[i],null);

rear=rear.next;

}

}

//输出方法

public String toString(){

String str=this.getClass().getName()+"(";

for(Nodep=this.head.next;p!=null;p=p.next)

{

str+=p.data.toString();

if(p.next!=null)

str+=",";

}

return str+=")";

}

//反转方法

public void reverse2(Node head){

Node p=head.next;

Node q=head.next.next;

head.next=null;

p.next=null;

while(q!=null){

Node temp=q.next;

q.next=p;

p=q;

q=temp;

}

q=this.head;

q.next=p;

/*

//想要直接在方法中遍历输出可http://以使用这段代码 ***p是反转后的第一个结点***

for(Node qq=p;qq!=null;qq=qq.next){//qq不能为q，因为结束循环后，p是最后一个结点，q是null

System.out.print(qq.data+"\t");

}

*/

}

public static void main(String[] args) {

Integer[] a={1,2,4,5,7};

SinglyList sl=new SinglyList<>(a);

System.out.println(sl.toString());

sl.reverse2(sl.head);

System.out.println(sl.toString());

}

}

输出结果：

{

rear.next=new Node(values[i],null);

rear=rear.next;

}

}

//输出方法

public String toString(){

String str=this.getClass().getName()+"(";

for(Nodep=this.head.next;p!=null;p=p.next)

{

str+=p.data.toString();

if(p.next!=null)

str+=",";

}

return str+=")";

}

//反转方法

public void reverse2(Node head){

Node p=head.next;

Node q=head.next.next;

head.next=null;

p.next=null;

while(q!=null){

Node temp=q.next;

q.next=p;

p=q;

q=temp;

}

q=this.head;

q.next=p;

/*

//想要直接在方法中遍历输出可http://以使用这段代码 ***p是反转后的第一个结点***

for(Node qq=p;qq!=null;qq=qq.next){//qq不能为q，因为结束循环后，p是最后一个结点，q是null

System.out.print(qq.data+"\t");

}

*/

}

public static void main(String[] args) {

Integer[] a={1,2,4,5,7};

SinglyList sl=new SinglyList<>(a);

System.out.println(sl.toString());

sl.reverse2(sl.head);

System.out.println(sl.toString());

}

}

输出结果：

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。