本文最后更新于：9 个月前
Leetcode 234. 回文链表
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
提示：
- 链表中节点数目在范围
[1, 105] 内
- 0 <= Node.val <= 9
进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
解析：
LeetCode234，这也是一道简单，但是很经典的链表题，判断一个链表是否为回文链表。
看到这个题你有几种思路解决，我们仍然是先将常见的数据结构和算法思想想一遍，看看谁能解决问题。
方法1
将链表元素都赋值到数组中，然后可以从数组两端向中间对比。这种方法会被视为逃避链表，面试不能这么干。
方法2
将链表元素全部压栈，然后一边出栈，一边重新遍历链表，一边比较两者元素值，只要有一个不相等，那就不是。
方法3
优化方法2，先遍历第一遍，得到总长度。之后一边遍历链表，一边压栈。到达链表长度一半后就不再压栈，而是一边出栈，一边遍历，一边比较，只要有一个不相等，就不是回文链表。这样可以节省一半的空间。
方法4
优化方法3:既然要得到长度，那还是要遍历一次链表才可以，那是不是可以一边遍历一边全部压栈，然后第二遍比较的时候，只比较一半的元素呢?也就是只有一半的元素出栈，链表也只遍历一半，当然可以。
方法5
反转链表法，先创建一个链表newList，将原始链表oldList的元素值逆序保存到newList中，然后重新一边遍历两个链表，一遍比较元素的值，只要有一个位置的元素值不一样，就不是回文链表。
方法6
优化方法5，我们只反转一半的元素就行了。先遍历一遍，得到总长度。然后重新遍历，到达一半的位置后不再反转，就开始比较两个链表。
方法7
优化方法6，我们使用双指针思想里的快慢指针，fast一次走两步，slow一次走一步。当fast到达表尾的时候，slow正好到达一半的位置，那么接下来可以从头开始逆序一半的元素，或者从slow开始逆序一半的元素，都可以。
方法8
在遍历的时候使用递归来反转一半链表可以吗? 当然可以，再组合一下我们还能想出更多的方法解决问题的思路不止这些了，此时单纯增加解法数量没啥意义了。
代码：
方法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
|
public static boolean isPalindromeByTwoPoints(ListNode head) {
if (head == null || head.next == null) {
return true;
}
ListNode slow = head, fast = head;
ListNode pre = head, prepre = null;
while (fast != null && fast.next != null) {
pre = slow;
slow = slow.next;
fast = fast.next.next;
pre.next = prepre;
prepre = pre;
}
if (fast != null) {
slow = slow.next;
}
while (pre != null && slow != null) {
if (pre.val != slow.val) {
return false;
}
pre = pre.next;
slow = slow.next;
}
return true;
}
|
方法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
|
public static boolean isPalindromeByAllStack(ListNode head) {
ListNode temp = head;
Stack<Integer> stack = new Stack();
while (temp != null) {
stack.push(temp.val);
temp = temp.next;
}
while (head != null) {
if (head.val != stack.pop()) {
return false;
}
head = head.next;
}
return true;
}
|
方法3：只将一半的数据压栈
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
|
public static boolean isPalindromeByHalfStack(ListNode head) {
if (head == null)
return true;
ListNode temp = head;
Stack<Integer> stack = new Stack();
int len = 0;
while (temp != null) {
stack.push(temp.val);
temp = temp.next;
len++;
}
len >>= 1;
while (len-- >= 0) {
if (head.val != stack.pop())
return false;
head = head.next;
}
return true;
}
|
方法4：通过递归来实现
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
|
public static boolean isPalindromeByRe(ListNode head) {
temp = head;
return check(head);
}
private static boolean check(ListNode head) {
if (head == null)
return true;
boolean res = check(head.next) && (temp.val == head.val);
temp = temp.next;
return res;
}
|
CSDN 发布文章
文章链接：https://blog.csdn.net/weixin_45876773/article/details/132832211
Leetcode 234. 回文链表
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
提示：
- 链表中节点数目在范围
[1, 105] 内
- 0 <= Node.val <= 9
进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
代码：
方法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
|
public static boolean isPalindromeByTwoPoints(ListNode head) {
if (head == null || head.next == null) {
return true;
}
ListNode slow = head, fast = head;
ListNode pre = head, prepre = null;
while (fast != null && fast.next != null) {
pre = slow;
slow = slow.next;
fast = fast.next.next;
pre.next = prepre;
prepre = pre;
}
if (fast != null) {
slow = slow.next;
}
while (pre != null && slow != null) {
if (pre.val != slow.val) {
return false;
}
pre = pre.next;
slow = slow.next;
}
return true;
}
|
方法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
|
public static boolean isPalindromeByAllStack(ListNode head) {
ListNode temp = head;
Stack<Integer> stack = new Stack();
while (temp != null) {
stack.push(temp.val);
temp = temp.next;
}
while (head != null) {
if (head.val != stack.pop()) {
return false;
}
head = head.next;
}
return true;
}
|
方法3：只将一半的数据压栈
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
|
public static boolean isPalindromeByHalfStack(ListNode head) {
if (head == null)
return true;
ListNode temp = head;
Stack<Integer> stack = new Stack();
int len = 0;
while (temp != null) {
stack.push(temp.val);
temp = temp.next;
len++;
}
len >>= 1;
while (len-- >= 0) {
if (head.val != stack.pop())
return false;
head = head.next;
}
return true;
}
|
方法4：通过递归来实现
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
|
public static boolean isPalindromeByRe(ListNode head) {
temp = head;
return check(head);
}
private static boolean check(ListNode head) {
if (head == null)
return true;
boolean res = check(head.next) && (temp.val == head.val);
temp = temp.next;
return res;
}
|
点击查看微信公众号【程序员小新儿】详细笔记