逆序思想
现假设有一链表,有待逆序操作。我们首先想到的就是将那个指针关系逆序了就行了呗。
事实上,就是这样。博主就是以这个为目标来完成的单链表逆序操作。
1
2
3
4
5
6
7
8
9
|
Node pre = null ;
Node post = null ;
while (head!= null ){
post = head.next;
head.next = pre;
pre = head;
head = post;
}
|
这便是逆序的核心了。下面我们就来一步步的讲解。
- 首次逆序:
一开始的话,pre,post都设置为null。这是必须的,因为在head.next=pre这行代码执行完成后,我们原始的那个head节点的next将变成null,也就是我们整个链表的null了。
想象一下,原来的那个链表的最后面的next不也是一个null吗?这里道理是一致的。
此时,更新pre为原来的head节点,也是为了下一步的逆序做准备,而head也自然的变成了原来的head.next了。
- 不断逆序。
抱歉,手抖了一下,画错了。大家见谅。手绘图上的第五次示意pre节点应该在节点5的位置,没有了head。
从图例中我们也不难看出,我们就是一次次的将head向后移,同时更新pre节点,来达到逆序的效果。
代码
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
|
package list;
public class ReverseList {
public static void main(String[] args) {
Node head = new Node( 1 );
int [] value = { 2 , 3 , 4 , 5 };
Node temp = head;
for ( int i = 0 ; i< value.length;i++) {
Node node = new Node(value[i]);
temp.next = node;
temp = temp.next;
}
printList(head);
// 反序输出一个单链表
head = reverse(head);
printList(head);
// 再次反向
head = reverseSingleList(head);
printList(head);
}
public static void printList(Node head) {
while (head!= null ) {
System.out.print( "\t" +head.value);
head = head.next;
}
System.out.println();
}
public static Node reverse(Node head) {
Node pre = null ;
Node post = null ;
while (head!= null ) {
post = head.next;
head.next = pre;
pre = head;
head = post;
}
return pre;
}
public static Node reverseSingleList(Node head) {
Node pre = null ;
Node next = null ;
while (head!= null ) {
next = head.next;
head.next = pre;
pre = head;
head = next;
}
return pre;
}
}
class Node {
public int value;
public Node next;
public Node( int value) {
this .value = value;
}
}
|
测试
经测试,代码输出正确。
1 2 3 4 5
5 4 3 2 1
1 2 3 4 5
帮助理解,下面是另一个实例:
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
|
/**
* java 实现单链表的逆序
* @author Administrator
*
*/
public class SingleLinkedReverse {
class Node{
int data;
Node next;
public Node( int data){
this .data = data;
}
}
public static void main(String[] args) {
SingleLinkedReverse slr = new SingleLinkedReverse();
Node head, tail;
head = tail = slr. new Node( 0 );
for ( int i= 1 ; i< 10 ; i++){
Node p = slr. new Node(i);
tail.next = p;
tail = p;
}
tail = head;
while (tail != null ){
System.out.print(tail.data+ " " );
tail = tail.next;
}
head = reverse(head);
System.out.println( " " );
while (head != null ){
System.out.print(head.data+ " " );
head = head.next;
}
}
private static Node reverse(Node head) {
Node p1,p2 = null ;
p1 = head;
while (head.next != null ){
p2 = head.next;
head.next = p2.next;
p2.next = p1;
p1 = p2;
}
return p2;
}
}
|
测试结果:
0 1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1 0
总结
以上就是本文关于java单链表逆序用法代码示例的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题,如有不足之处,欢迎留言指出。感谢朋友们对本站的支持!
原文链接:http://blog.csdn.net/marksinoberg/article/details/52490318