首页 > 编程语言 > 用JAVA实现单链表，检测字符串是否是回文串
2020
11-25

用JAVA实现单链表，检测字符串是否是回文串

一.需求

使用JAVA实现单链表，使用单链表检测字符串是否是回文串

二.需求分析

回文串最重要的就是对称，那么最重要的问题就是找到那个中心，用快指针每步走两格，当他到达链表末端的时候，慢指针刚好到达中心，慢指针在遍历过程中（快指针到达末端时）把走过的节点进行反向操作，此时从中位点分为前后两部分，此时前半部分的指针开始往回指（取next的时候，取的是前一个节点），而慢指针继续向前，跟前半部分的数据依次进行比对，当慢指针扫完整个链表，就可以判断这是回文串，否则就提前退出，同时在前半部分往回遍历的过程中将前半部分的指针重置成正向。

链表存在奇偶数情况。

奇数的时候，快指针遍历到末端的时候，中点位即中间位置的点，此中位点下一个节点为后半部分比对开始的位置。
偶数的时候，快指针遍历到末端的时候，中点位置此时为下中位点,此中位点就是后半部分比对开始的位置。

三.代码实现

1.单链表类封装

?
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
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
public class ListNode<T> {
 /**
  * 根节点索引位置
  */
 private int foot;
 /**
  * 代表链表程度
  */
 private int count;
 /**
  * 标识根节点
  */
 private Node root;
 
 //链接点类,内部方法实现，外部使用
 private class Node {
  //数据信息
  private T data;
  //下一个节点引用
  private Node next;
 
  public Node(T data) {
   this.data = data;
  }
 
  //添加节点
  private void add(T data) {
   if (this.next == null) {
    //如果当前节点的next为null,直接创建一个新的节点
    this.next = new Node(data);
   } else {
    //否则进行递归调用，直到最后在某个为空的节点创建一个新节点
    this.next.add(data);
   }
  }
 
  //删除节点1
  public void remove(Node previous, int index) {
 
   if (ListNode.this.foot++ == index) {
    //this表示当前要删除的节点
    previous.next = this.next;
    this.next = null;
    ListNode.this.count--;
    return;
   } else {
    //递归删除
    this.next.remove(this, index);
   }
 
  }
 
  //删除节点2
  public void remove(Node previous, T data) {
   if (this.data.equals(data)) {
    previous.next = this.next;
    this.next = null;
    ListNode.this.count--;
    return;
   } else {
    if (this.next != null) {
     this.next.remove(this, data);
    } else {
     return;
    }
   }
  }
 
  //修改数据 -- 新数据替换旧数据
  public void replace(T oldData, T newData) {
   if (this.data.equals(newData)) {
    this.data = newData;
   } else {
    //递归修改，寻找当前节点下一个节点，直到某个节点的值匹配入参
    this.next.replace(oldData, newData);
   }
 
  }
 
  //修改数据 -- 利用索引修改
  public void replace(int index, T newData) {
   if (ListNode.this.foot++ == index) {
    //找到了某个值的索引和传入的索引相同，直接替换
    this.data = newData;
   } else {
    this.next.replace(index, newData);
   }
  }
 
  //查询
  public T get(int index) {
   if (ListNode.this.foot++ == index) {
    return this.data;
   } else {
    return this.next.get(index);
   }
  }
 
  //链表是否包含某个节点
  public boolean contains(T data) {
   //如果当前的这个data正好和传入的data匹配
   if (this.data.equals(data)) {
    return true;
   } else {
    //如果当前的这个不匹配，则需要查找下一个节点
    if (this.next == null) {
     return false;
    } else {
     return this.next.contains(data);
    }
   }
  }
 
 }
 
 public ListNode() {
 
 }
 
 //检查链表是否为空
 public boolean isEmpty() {
  if (count == 0 || this.root == null) {
   return true;
  } else {
   return false;
  }
 }
 
 //获取链表的长度
 public int size() {
  return this.count;
 }
 
 //添加
 public void add(T data) {
  if (this.isEmpty()) { //如果链表为空，新建一个节点
   this.root = new Node(data);
  } else {
   this.root.add(data);
  }
  this.count++;
 }
 
 //删除 -- 按照索引删除
 public void remove(int index) {
  if (this.isEmpty()) {
   return;
  }
  if (index < 0 || this.count <= index) {
   return;
  }
  if (index == 0) { //想要删除根节点
   Node temp = this.root;
   this.root = this.root.next;
   temp.next = null;
   this.count--;
   return;
  } else {
   this.foot = 0;
   this.root.remove(this.root, index);
  }
 }
 
 //根据传入的数值删除
 public void remove(T data) {
  if (this.isEmpty()) {
   return;
  }
  //如果删除的正好是根节点
  if (this.root.data.equals(data)) {
   Node temp = this.root;
   this.root = this.root.next;
   temp.next = null;
   this.count--;
   return;
  } else {
   this.root.remove(this.root, data);
  }
 }
 
 //修改 -- 根据索引修改
 public void replace(int index, T newData) {
  if (this.isEmpty()) {
   return;
  }
  if (index < 0 || this.count <= index) {
   return;
  }
  this.foot = 0;
  this.root.replace(index, newData);
 }
 
 //修改 -- 新老数据替换
 public void replace(T oldData, T newData) {
  if (this.isEmpty()) {
   return;
  }
  this.root.replace(oldData, newData);
 }
 
 //查询 --- 根据索引查找
 public T get(int index) {
  if (this.isEmpty()) {
   return null;
  }
  this.foot = 0;
  return this.root.get(index);
 }
 
 //是否包含
 public boolean contains(T data) {
  if (this.isEmpty()) {
   return false;
  }
  return this.root.contains(data);
 }
 
 //打印 toArray
 public Object[] toArray() {
  if (this.isEmpty()) {
   return null;
  }
  int count = this.count;
  Object[] retVal = new Object[count];
  for (int i = 0; i < count; i++) {
   retVal[i] = this.get(i);
  }
  return retVal;
 }
}

2.验证的具体方法

?
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
boolean isPalindrome(ListNode.Node head) {
 if (head == null || head.next == null) {
  return true;
 }
 //
 ListNode.Node prev = null;
 //慢指针节点
 ListNode.Node slow = head;
 //快指针节点
 ListNode.Node fast = head;
 //奇数的中位节点或者是偶数的下中位节点
 ListNode.Node middle = head;
 while (fast != null && fast.next != null) {
  //快指针每次移动2个节点
  fast = fast.next.next;
  //慢指针每次移动1个节点
  ListNode.Node next = slow.next;
  //前半部分的指针反向。反向后前半部分节点的next节点都是他的前一个节点
  slow.next = prev;
  //当前的慢指针指向前一个节点
  prev = slow;
  //下一个节点变为慢节点
  slow = next;
  //记录中位节点
  middle = slow;
 }
 //如果fast不是null，说明此时有奇数个节点，偶数个节点时fast为null
 //还没有进行if处理之前slow节点和prev节点在奇偶数的情况下分别为
 // a b c d c b a 此种情况下slow节点是d，prev节点是第1个c
 // a b c c b a 此种情况下slow节点是第2个c，prev节点是第1个c
 if (fast != null) {
  //slow取中间节点的下一个节点，做为回文比较的起点
  slow = slow.next;
 }
 //进行if处理结束之后，slow代表的是后半段的第一个节点，指针向后移动
 //prev代表的是前半段的最后一个节点，指针向前移动
 // a b c d c b a 此种情况下slow节点是第2个c，prev节点是第1个c
 // a b c c b a 此种情况下slow节点是第2个c，prev节点是第1个c
 //前半部分指针恢复正常处理。将下一个节点记录下来
 ListNode.Node next = middle;
 while (slow != null) {
  //进行数据比对。如果不相等则不是回文
  if (slow.data != prev.data) {
  return false;
  }
  //前半部分当前节点
  ListNode.Node current = prev;
  //prev向前取节点
  prev = prev.next;
  //slow向后取节点
  slow = slow.next;
  //前半部分指针恢复正常处理。
  current.next = next;
  //本轮处理完之后，将next赋值为当前节点
  next = current;
 }
 return true;
}

四.代码测试

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void main(String[] args) {
 ListNode<String> listNode = new ListNode<String>();
 listNode.add("a");
 listNode.add("b");
 listNode.add("c");
 listNode.add("d");
 listNode.add("e");
 listNode.add("f");
 listNode.add("e");
 listNode.add("d");
 listNode.add("c");
 listNode.add("b");
 listNode.add("a");
 ListNode example = new ListNode();
 boolean b = example.isPalindrome(listNode.root);
 System.out.println("是否是回文：" + b);//true
}

五.完整代码

?
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
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
public class ListNode<T> {
 /**
  * 根节点索引位置
  */
 private int foot;
 /**
  * 代表链表程度
  */
 private int count;
 /**
  * 标识根节点
  */
 private Node root;
 
 //链接点类,内部方法实现，外部使用
 private class Node {
  //数据信息
  private T data;
  //下一个节点引用
  private Node next;
 
  public Node(T data) {
   this.data = data;
  }
 
  //添加节点
  private void add(T data) {
   if (this.next == null) {
    //如果当前节点的next为null,直接创建一个新的节点
    this.next = new Node(data);
   } else {
    //否则进行递归调用，直到最后在某个为空的节点创建一个新节点
    this.next.add(data);
   }
  }
 
  //删除节点1
  public void remove(Node previous, int index) {
 
   if (ListNode.this.foot++ == index) {
    //this表示当前要删除的节点
    previous.next = this.next;
    this.next = null;
    ListNode.this.count--;
    return;
   } else {
    //递归删除
    this.next.remove(this, index);
   }
 
  }
 
  //删除节点2
  public void remove(Node previous, T data) {
   if (this.data.equals(data)) {
    previous.next = this.next;
    this.next = null;
    ListNode.this.count--;
    return;
   } else {
    if (this.next != null) {
     this.next.remove(this, data);
    } else {
     return;
    }
   }
  }
 
  //修改数据 -- 新数据替换旧数据
  public void replace(T oldData, T newData) {
   if (this.data.equals(newData)) {
    this.data = newData;
   } else {
    //递归修改，寻找当前节点下一个节点，直到某个节点的值匹配入参
    this.next.replace(oldData, newData);
   }
 
  }
 
  //修改数据 -- 利用索引修改
  public void replace(int index, T newData) {
   if (ListNode.this.foot++ == index) {
    //找到了某个值的索引和传入的索引相同，直接替换
    this.data = newData;
   } else {
    this.next.replace(index, newData);
   }
  }
 
  //查询
  public T get(int index) {
   if (ListNode.this.foot++ == index) {
    return this.data;
   } else {
    return this.next.get(index);
   }
  }
 
  //链表是否包含某个节点
  public boolean contains(T data) {
   //如果当前的这个data正好和传入的data匹配
   if (this.data.equals(data)) {
    return true;
   } else {
    //如果当前的这个不匹配，则需要查找下一个节点
    if (this.next == null) {
     return false;
    } else {
     return this.next.contains(data);
    }
   }
  }
 
 }
 
 public ListNode() {
 
 }
 
 //检查链表是否为空
 public boolean isEmpty() {
  if (count == 0 || this.root == null) {
   return true;
  } else {
   return false;
  }
 }
 
 //获取链表的长度
 public int size() {
  return this.count;
 }
 
 //添加
 public void add(T data) {
  if (this.isEmpty()) { //如果链表为空，新建一个节点
   this.root = new Node(data);
  } else {
   this.root.add(data);
  }
  this.count++;
 }
 
 //删除 -- 按照索引删除
 public void remove(int index) {
  if (this.isEmpty()) {
   return;
  }
  if (index < 0 || this.count <= index) {
   return;
  }
  if (index == 0) { //想要删除根节点
   Node temp = this.root;
   this.root = this.root.next;
   temp.next = null;
   this.count--;
   return;
  } else {
   this.foot = 0;
   this.root.remove(this.root, index);
  }
 }
 
 //根据传入的数值删除
 public void remove(T data) {
  if (this.isEmpty()) {
   return;
  }
  //如果删除的正好是根节点
  if (this.root.data.equals(data)) {
   Node temp = this.root;
   this.root = this.root.next;
   temp.next = null;
   this.count--;
   return;
  } else {
   this.root.remove(this.root, data);
  }
 }
 
 //修改 -- 根据索引修改
 public void replace(int index, T newData) {
  if (this.isEmpty()) {
   return;
  }
  if (index < 0 || this.count <= index) {
   return;
  }
  this.foot = 0;
  this.root.replace(index, newData);
 }
 
 //修改 -- 新老数据替换
 public void replace(T oldData, T newData) {
  if (this.isEmpty()) {
   return;
  }
  this.root.replace(oldData, newData);
 }
 
 //查询 --- 根据索引查找
 public T get(int index) {
  if (this.isEmpty()) {
   return null;
  }
  this.foot = 0;
  return this.root.get(index);
 }
 
 //是否包含
 public boolean contains(T data) {
  if (this.isEmpty()) {
   return false;
  }
  return this.root.contains(data);
 }
 
 //打印 toArray
 public Object[] toArray() {
  if (this.isEmpty()) {
   return null;
  }
  int count = this.count;
  Object[] retVal = new Object[count];
  for (int i = 0; i < count; i++) {
   retVal[i] = this.get(i);
  }
  return retVal;
 }
 
 boolean isPalindrome(ListNode.Node head) {
  if (head == null || head.next == null) {
   return true;
  }
  //
  ListNode.Node prev = null;
  //慢指针节点
  ListNode.Node slow = head;
  //快指针节点
  ListNode.Node fast = head;
  //奇数的中位节点或者是偶数的下中位节点
  ListNode.Node middle = head;
  while (fast != null && fast.next != null) {
   //快指针每次移动2个节点
   fast = fast.next.next;
   //慢指针每次移动1个节点
   ListNode.Node next = slow.next;
   //前半部分的指针反向。反向后前半部分节点的next节点都是他的前一个节点
   slow.next = prev;
   //当前的慢指针指向前一个节点
   prev = slow;
   //下一个节点变为慢节点
   slow = next;
   //记录中位节点
   middle = slow;
  }
  //如果fast不是null，说明此时有奇数个节点，偶数个节点时fast为null
  //还没有进行if处理之前slow节点和prev节点在奇偶数的情况下分别为
  // a b c d c b a 此种情况下slow节点是d，prev节点是第1个c
  // a b c c b a 此种情况下slow节点是第2个c，prev节点是第1个c
  if (fast != null) {
   //slow取中间节点的下一个节点，做为回文比较的起点
   slow = slow.next;
  }
  //进行if处理结束之后，slow代表的是后半段的第一个节点，指针向后移动
  //prev代表的是前半段的最后一个节点，指针向前移动
  // a b c d c b a 此种情况下slow节点是第2个c，prev节点是第1个c
  // a b c c b a 此种情况下slow节点是第2个c，prev节点是第1个c
  //前半部分指针恢复正常处理。将下一个节点记录下来
  ListNode.Node next = middle;
  while (slow != null) {
   //进行数据比对。如果不相等则不是回文
   if (slow.data != prev.data) {
    return false;
   }
   //前半部分当前节点
   ListNode.Node current = prev;
   //prev向前取节点
   prev = prev.next;
   //slow向后取节点
   slow = slow.next;
   //前半部分指针恢复正常处理。
   current.next = next;
   //本轮处理完之后，将next赋值为当前节点
   next = current;
  }
  return true;
 }
 
 public static void main(String[] args) {
  ListNode<String> listNode = new ListNode<String>();
  listNode.add("a");
  listNode.add("b");
  listNode.add("c");
  listNode.add("d");
  listNode.add("e");
  listNode.add("f");
  listNode.add("e");
  listNode.add("d");
  listNode.add("c");
  listNode.add("b");
  listNode.add("a");
  ListNode example = new ListNode();
  boolean b = example.isPalindrome(listNode.root);
  System.out.println("是否是回文：" + b);
 }
}

以上就是使用JAVA实现单链表，检测字符串是否是回文串的详细内容，更多关于java封装单链表的资料请关注自学编程网其它相关文章！

编程技巧