| 题目链接 | 234. 回文链表 |
|---|---|
| 思路 | 链表综合题：快慢指针 + 指针翻转 |
| 题解链接 | 官方题解 |
| 关键点 | while fast.next and fast.next.next: ... |
| 时间复杂度 | \(O(n)\) |
| 空间复杂度 | \(O(1)\) |
代码实现：
class Solution:
def isPalindrome(self, head: Optional[ListNode]) -> bool:
if head is None:
return True
first = self.halfList(head)
second = self.reverseList(first.next)
answer = True
cur_first, cur_second = head, second
while answer and cur_second:
if cur_first.val != cur_second.val:
answer = False
break
cur_first = cur_first.next
cur_second = cur_second.next
first.next = self.reverseList(second)
return answer
def halfList(self, head):
slow = fast = head
while fast.next and fast.next.next:
fast = fast.next.next
slow = slow.next
return slow
def reverseList(self, head):
previous = None
current = head
while current:
next_node = current.next
current.next = previous
previous = current
current = next_node
return previous