Keep and carry on.

用java对数据结构单向链表的实现,其中定义了两个数据结构,链表Link和节点ListNode

1
2
3
4
ListNode head=null;
public Link(ListNode n){
head=n;
}
1
2
3
4
5
6
7
public class ListNode {
ListNode next=null;
int data;
public ListNode(int data){
this.data=data;
}
}

对链表有如下操作:

1、链表末尾插入数据

2、删除第index个节点

3、返回节点长度

4、在不知道头指针的情况下删除指定节点

5、打印节点

6、链表反转

7、查找单链表的中间结点

8、查找倒数第k个节点

9、对列表进行排序

10、删除重复节点

11、从尾到头输出单链表

实现代码如下:

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
/**
* 链表末尾插入数据
* @param d
*/
public void addNode(int d){
ListNode n=new ListNode(d);
if(this.head==null){
this.head=n;
}
else{
ListNode tmp=this.head;
while(tmp.next!=null){
tmp=tmp.next;
}
tmp.next=n;
}
}
public void addNode(ListNode n){
if(this.head==null)this.head=n;
else{
ListNode tmp=this.head;
while(tmp.next!=null){
tmp=tmp.next;
}
tmp.next=n;
}
}
/*
* 删除第index个节点
*/
public boolean deleteNode(int index){
int i=1;
if(index<1||index>length())return false;
if(index==1){
this.head=this.head.next;
return true;
}
ListNode preNode=this.head;
ListNode curNode=preNode.next;
while(curNode!=null){
if(i==index-1){
preNode.next=curNode.next;
return true;
}
preNode=curNode;
curNode=curNode.next;
i++;
}
return false;
}
/*
* 返回节点长度
*/
public int length(){
int length=0;
ListNode tmp=this.head;
while(tmp!=null){
length++;
tmp=tmp.next;
}
return length;
}
/*
* 在不知道头指针的情况下删除指定节点
*/
public boolean deleteNode1(ListNode n){
if(n==null||n.next==null)return false;
n.data=n.next.data;
n.next=n.next.next;
return true;
}
/*
* 打印节点
*/
public void printList(){
ListNode tmp=this.head;
while(tmp!=null){
System.out.print(tmp.data+" ");
tmp=tmp.next;
}
System.out.println();
}
/*
* 链表反转
*/
public Link ReverseIteratively(){
ListNode pNode=this.head;
ListNode pPrev=null;
Link newLink = null;
while(pNode!=null){
ListNode pNext=pNode.next;
if(pNext==null){
newLink=new Link(pNode);
}
pNode.next=pPrev;
pPrev=pNode;
pNode=pNext;
}
return newLink;
}
/*
* 查找单链表的中间结点
* 采用快慢指针的方式查找单链表的中间节点,快指针一次走两步,慢指针一次走一步,当快指针走完时,慢指针刚好到达中间节点。
*/
public ListNode SearchMid(){
ListNode fast=this.head;
ListNode low=this.head;
while(fast!=null&&fast.next!=null&&fast.next.next!=null){
fast=fast.next.next;
low=low.next;
}
System.out.println(low.data);
return low;
}
/*
* 查找倒数第k个节点
* 采用两个指针P1,P2,P1先前移K步,然后P1、P2同时移动,当p1移动到尾部时,P2所指位置的元素即倒数第k个元素 。
*/
public ListNode findElem(ListNode head, int k){
if(k<1||k>this.length())return null;
int index=0;
ListNode p=head;
ListNode q=head;
for(int i=0;i<k;i++){
q=q.next;
}
while(q!=null){
p=p.next;
q=q.next;
}
System.out.println(p.data);
return p;
}
/*
* 对列表进行排序
*/
public void SortList(){
ListNode curNode=this.head;
ListNode nextNode=null;
int tmp=0;
while(curNode.next!=null){
nextNode=curNode.next;
while(nextNode!=null){
if(curNode.data>nextNode.data){
tmp=curNode.data;
curNode.data=nextNode.data;
nextNode.data=tmp;
}
nextNode=nextNode.next;
}
curNode=curNode.next;
}
}
/*
* 删除重复节点
*/
public void deleteDuplecate(){
ListNode curNode=this.head;
ListNode nextNode=null;
while(curNode.next!=null){
nextNode=curNode;
while(nextNode.next!=null){
if(curNode.data==nextNode.next.data){
nextNode.next=nextNode.next.next;
}else
nextNode=nextNode.next;
}
curNode=curNode.next;
}
}
/*
* 从尾到头输出单链表,采用递归方式
*/
public void printListReversely(ListNode node){
if(node.next!=null){
printListReversely(node.next);
}
System.out.println(node.data);
}
Read More
⬆︎TOP