力扣第 234 题
题目
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
示例 1：
输入：head = [1,2,2,1]
输出：true
示例 2：
输入：head = [1,2]
输出：false
提示：
- 链表中节点数目在范围
[1, 105] 内
0 <= Node.val <= 9
进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
分析
#1
用额外空间的话很简单。
1
2
3
4
5
6
7
|
class Solution:
def isPalindrome(self, head: Optional[ListNode]) -> bool:
A,p = [],head
while p:
A.append(p.val)
p=p.next
return A[::-1]==A
|
282 ms
#2
不用额外空间，类似 0143:
- 先用快慢节点找到中点位置，截断为两部分
- 将后半部分链表反转后和前半部分对比即可
解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
class Solution:
def isPalindrome(self, head: Optional[ListNode]) -> bool:
def reverse(head):
tail = head
while tail and tail.next:
tmp = tail.next
tail.next = tmp.next
tmp.next = head
head = tmp
return head
slow = fast = ListNode(next=head)
while fast and fast.next:
slow, fast = slow.next, fast.next.next
q = slow.next
slow.next = None
p, q = head, reverse(q)
while q:
if p.val!=q.val:
return False
p,q = p.next,q.next
return True
|
275 ms