题目描述

[EN | CN]

请判断一个链表是否为回文链表。

示例 1:

1
2
输入: 1->2
输出: false

示例 2:

1
2
输入: 1->2->2->1
输出: true

进阶:

你能否用 $O(n)$ 时间复杂度和 $O(1)$ 空间复杂度解决此题?

解法 1:反转链表的一半后比较

判断是否回文链表就是判断前一半反转之后是否等于后一半,那么思路就比较直接:

  1. 首先利用快慢指针遍历整个链表,并且反转慢指针遍历的链表,当快指针走到尽头时,说明此时慢指针走到链表中间,停止反转;
  2. 从慢指针处开始遍历原链表的后一半,在遍历的过程中不断比对「原链表的结点」与「链表前半部分的反转的对应结点」。

题目要求空间复杂度为 $O(1)$,而我们又需要反转链表,所以…… 只能是先反转原链表,然后在遍历对比的时候把它反转回来(下面没有实现恢复这一步)。

注意链表长度为奇数或者偶数的情况有一点点不同。

假设链表长度为 $n$,那么

  • 时间复杂度为 $O(n)$,遍历一遍;
  • 空间复杂度为 $O(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
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        reve = None
        fast = slow = head

        # Find the middle and reverse the first half
        while fast is not None and fast.next is not None:
            fast = fast.next.next
            temp = slow.next
            slow.next = reve
            reve = slow
            slow = temp
        if fast is not None:  # Odd length
            slow = slow.next

        # Compare
        while reve is not None and reve.val == slow.val:
            reve = reve.next
            slow = slow.next

        return reve is None
  • Runtime: 72 ms, faster than 94.19% of Python3 online submissions for Palindrome Linked List.
  • Memory Usage: 24.2 MB, less than 7.69% of Python3 online submissions for Palindrome Linked List.