Willow's blog

单链表原地反序

「原地」指的是除给出类之外,不借助其他的辅助结构

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
58
59
60
61
/** 带头指针的单链表原地逆序(逆序函数为reverse)
* Created by Willow on 1/5/17.
*/
public class List {
Node head;
public List(Node head) {
this.head = head;
}
//节点
static class Node {
int data;
Node next;
public Node() {}
public Node(int data, Node next) {
this.data = data;
this.next = next;
}
}
//逆序
public void reverse() {
if (null == head || null == head.next || null == head.next.next)
return;
Node pre = null, cur = this.head.next, nex = cur.next;
while (null != nex) {
//1. 逆置当前节点指向
cur.next = pre;
//2. 前置、当前、后置节点的三个指针向前移动
pre = cur;
cur = nex;
nex = nex.next;
}
cur.next = pre;//3. 逆置最后一个节点的指向
this.head.next = cur;//4. 头指针指向最后一个节点
}
//遍历
public void traverse() {
if (null == head.next)
return;
Node cur = head.next;
while (null != cur) {
System.out.println(cur.data);
cur = cur.next;
}
System.out.println("traverse end \n");
}
//测试入口
public static void main(String[] args) {
Node n7 = new Node(7, null);
Node n6 = new Node(6, n7);
Node n5 = new Node(5, n6);
Node n4 = new Node(4, n5);
Node n3 = new Node(3, n4);
Node n2 = new Node(2, n3);
Node n1 = new Node(1, n2);
Node head = new Node(0, n1);
List list = new List(head);
list.traverse();
list.reverse();
list.traverse();
}
}
(EOF)
杨威
发布日期 :2017-01-20
自由转载-非商用-非衍生-保持署名(知识共享3.0许可证)
杨威 wechat
微信订阅号
写点什么 心里不慌