文章目录
题目
标题和出处
标题：回文链表
出处：234. 回文链表
难度
3 级
题目描述
要求
给你单链表的头结点 head \texttt{head} head，如果是回文链表，返回 true \texttt{true} true。
示例
示例 1：
输入：
head
=
[1,2,2,1]
\texttt{head = [1,2,2,1]}
head = [1,2,2,1]
输出：
true
\texttt{true}
true
示例 2：
输入：
head
=
[1,2]
\texttt{head = [1,2]}
head = [1,2]
输出：
false
\texttt{false}
false
数据范围
- 链表中结点的数目范围是 [1, 10 5 ] \texttt{[1, 10}^\texttt{5}\texttt{]} [1, 105]
- 0 ≤ Node.val ≤ 9 \texttt{0} \le \texttt{Node.val} \le \texttt{9} 0≤Node.val≤9
进阶
你能否使用 O(n) \texttt{O(n)} O(n) 时间和 O(1) \texttt{O(1)} O(1) 空间解决这道题？
解法一
思路和算法
最直观的方法是用数组存储链表中的每个结点的值，然后判断数组中的元素是否构成回文。遍历列表，将每个结点的值依次加入数组 nums \textit{nums} nums，此时数组中的元素顺序和链表的每个结点的值的顺序一致。
假设链表的结点数是 size \textit{size} size，则数组 nums \textit{nums} nums 的长度也是 size \textit{size} size。数组 nums \textit{nums} nums 中的元素构成回文，当且仅当对任意 0 ≤ i < size 0 \le i < \textit{size} 0≤i<size 都有 nums [ i ] = nums [ size − 1 − i ] \textit{nums}[i] = \textit{nums}[\textit{size} - 1 - i] nums[i]=nums[size−1−i]。
在判断数组中的元素是否构成回文时，只需要考虑 i < size − 1 − i i < \textit{size} - 1 - i i<size−1−i 的情况，等价于 i < size − 1 2 i < \dfrac{\textit{size} - 1}{2} i<2size−1。因此只需要对 0 ≤ i ≤ ⌊ size − 1 2 ⌋ 0 \le i \le \Big\lfloor\dfrac{\textit{size} - 1}{2} \Big\rfloor 0≤i≤⌊2size−1⌋ 的情况判断对应元素是否相等即可。
代码
class Solution {
public boolean isPalindrome(ListNode head) {
List<Integer> nums = new ArrayList<Integer>();
ListNode node = head;
while (node != null) {
nums.add(node.val);
node = node.next;
}
int size = nums.size();
for (int i = (size - 1) / 2; i >= 0; i--) {
int j = size - 1 - i;
if (nums.get(i) != nums.get(j)) {
return false;
}
}
return true;
}
}
复杂度分析
-
时间复杂度： O ( n ) O(n) O(n)，其中 n n n 是链表的长度。需要遍历链表中的每个结点一次，将结点值加入数组，然后需要遍历数组判断是否构成回文。
-
空间复杂度： O ( n ) O(n) O(n)，其中 n n n 是链表的长度。需要创建长度为 n n n 的数组存储链表中每个结点的值。
解法二
思路和算法
为了将空间复杂度降低到 O ( 1 ) O(1) O(1)，不能使用数组存储链表的结点值，而是需要将链表的一半反转，然后比较链表的前后两半是否相同。
为了将链表的一半反转，需要首先找到链表的中间结点。可以使用「链表的中间结点」的快慢指针的做法，使用 O ( 1 ) O(1) O(1) 空间找到链表的中间结点，当链表的结点数是偶数时，得到的是链表的第二个中间结点。快慢指针遍历结束时，快指针 fast \textit{fast} fast 移动到链表的尾结点或者空结点，慢指针 slow \textit{slow} slow 移动到链表的中间结点。
链表的前一半为 slow \textit{slow} slow 前面的部分，不包含 slow \textit{slow} slow，链表的后一半则由链表结点数的奇偶性决定：
-
当链表的结点数是奇数时，链表的后一半从 slow . next \textit{slow}.\textit{next} slow.next 开始，此时链表的中间结点既不属于前一半也不属于后一半，其余每个结点都属于前一半或者后一半；
-
当链表的结点数是偶数时，链表的后一半从 slow \textit{slow} slow 开始，此时链表的每个结点都属于前一半或者后一半。
确定链表的前一半和后一半之后，将链表的前一半反转，即反转 slow \textit{slow} slow 前面的部分，反转的部分不包含 slow \textit{slow} slow。反转链表的做法可以使用「反转链表」的迭代解法，使得空间复杂度为 O ( 1 ) O(1) O(1)。
将前一半反转之后，同时遍历链表的两半（注意前一半已经反转），则每次遍历到的两个结点为原始链表中关于中心对称的结点。当且仅当每次遍历到的两个结点的值相等时，原始链表是回文链表。
当链表结点数是奇数时，考虑如下链表：
1 → 2 → 3 → 2 → 1 1 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 1 1→2→3→2→1
将前一半反转之后变成：
1 ← 2 3 → 2 → 1 1 \leftarrow 2 \quad \ ~ 3 \rightarrow 2 \rightarrow 1 1←2 3→2→1
分别从两个结点 2 2 2 开始遍历链表的两半。
当链表结点数是偶数时，考虑如下链表：
1 → 2 → 3 → 3 → 2 → 1 1 \rightarrow 2 \rightarrow 3 \rightarrow 3 \rightarrow 2 \rightarrow 1 1→2→3→3→2→1
将前一半反转之后变成：
1 ← 2 ← 3 3 → 2 → 1 1 \leftarrow 2 \leftarrow 3 \quad \ ~ 3 \rightarrow 2 \rightarrow 1 1←2←3 3→2→1
分别从两个结点 3 3 3 开始遍历链表的两半。
代码
class Solution {
public boolean isPalindrome(ListNode head) {
ListNode fast = head, slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
boolean odd = fast != null;
ListNode firstHalfEnd = slow;
ListNode secondHalfStart = odd ? slow.next : slow;
ListNode node1 = reverseFirstHalf(head, firstHalfEnd);
ListNode node2 = secondHalfStart;
while (node1 != null) {
if (node1.val != node2.val) {
return false;
}
node1 = node1.next;
node2 = node2.next;
}
return true;
}
public ListNode reverseFirstHalf(ListNode head, ListNode firstHalfEnd) {
ListNode prev = null, curr = head;
while (curr != firstHalfEnd) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
}
复杂度分析
-
时间复杂度： O ( n ) O(n) O(n)，其中 n n n 是链表的长度。需要使用快慢指针遍历链表，遍历链表的前一半并反转，以及反转后遍历链表，每次遍历的时间复杂度都是 O ( n ) O(n) O(n)。
-
空间复杂度： O ( 1 ) O(1) O(1)。