目录

0234:回文链表

力扣第 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