Java带头结点的单链表 Java 反转带头结点的单链表并显示输出的实现过程
吉吉女王 人气:0想了解Java 反转带头结点的单链表并显示输出的实现过程的相关内容吗,吉吉女王在本文为您仔细讲解Java带头结点的单链表的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点:Java带头结点的单链表,Java,反转单链表,下面大家一起来学习吧。
注意:要保证已经有Node类和单链表的初始化,这样才能调用反转方法并显示结果。
方法如下:
//Node<T>指泛型结点类 public void reverse2(Node<T> head){ Node<T> p=head.next; Node<T> q=head.next.next; head.next=null; p.next=null; while(q!=null){ Node<T> temp=q.next; q.next=p; p=q; q=temp; } q=this.head; q.next=p; /* //想要直接在方法中遍历输出可以使用这段代码 ***p是反转后的第一个结点*** for(Node<T> 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<T>{ public T data; public Node<T>next; public Node(T data,Node<T>next){ this.data=data; this.next=next; } public Node(){ this(null,null); } public String toString(){ return this.data.toString(); } }
单链表类:
public class SinglyList<T> { public Node<T> head; public SinglyList(){ this.head=new Node<T>(); } public SinglyList(T[] values){ this(); Node<T> rear=this.head; for(int i=0;i<values.length;i++) { rear.next=new Node<T>(values[i],null); rear=rear.next; } } //输出方法 public String toString(){ String str=this.getClass().getName()+"("; for(Node<T>p=this.head.next;p!=null;p=p.next) { str+=p.data.toString(); if(p.next!=null) str+=","; } return str+=")"; } //反转方法 public void reverse2(Node<T> head){ Node<T> p=head.next; Node<T> q=head.next.next; head.next=null; p.next=null; while(q!=null){ Node<T> temp=q.next; q.next=p; p=q; q=temp; } q=this.head; q.next=p; /* //想要直接在方法中遍历输出可以使用这段代码 ***p是反转后的第一个结点*** for(Node<T> 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<Integer> sl=new SinglyList<>(a); System.out.println(sl.toString()); sl.reverse2(sl.head); System.out.println(sl.toString()); } }
输出结果:
加载全部内容