问题描述
给定一个链表，要求判断链表是否是一个回文链表。题目链接：点我
样例输入输出
输入：head = [1,2,2,1]
输出：true
输入：head = [1,2]
输出：false
问题解法
此题最简单的做法是将链表转成数组，然后按回文数组进行判断。但是这样空间复杂度是 O(n)，可以进一步优化：将链表分成前后两半，然后翻转其中一半的链表，将这两个链表进行比较，比较结束后恢复翻转的链表。代码如下
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
|
class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) {
return true;
}
ListNode quick = head.next;
ListNode slow = head;
while (quick.next != null && quick.next.next != null) {
quick = quick.next.next;
slow = slow.next;
}
ListNode secondHead = slow.next;
slow.next = null;
ListNode firstHead = reverse(head);
boolean result;
if (quick.next != null) {
result = isEqual(firstHead, secondHead.next);
} else {
result = isEqual(firstHead, secondHead);
}
reverse(firstHead);
slow.next = secondHead;
return result;
}
private boolean isEqual(ListNode first, ListNode second) {
while (first != null && second != null) {
if (first.val != second.val) {
return false;
}
first = first.next;
second = second.next;
}
return first == null && second == null;
}
private ListNode reverse(ListNode head) {
ListNode dummy = new ListNode(-1, head);
ListNode other = new ListNode();
while (dummy.next != null) {
ListNode dummyNext = dummy.next;
dummy.next = dummyNext.next;
dummyNext.next = other.next;
other.next = dummyNext;
}
return other.next;
}
}
|