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

151 阅读 0 评论 100 点赞

我是靠谱客的博主哭泣白开水，这篇文章主要介绍Java 反转带头结点的单链表并显示输出的实现过程，现在分享给大家，希望可以做个参考。

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

方法如下：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//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类：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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());
}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
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());
}
}