[LeetCode]234. 回文链表(Palindrome Linked List)

题目描述

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

示例 1:

输入: 1->2
输出: false

示例 2:

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

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

解题思路

使用快慢指针,对于慢指针走过的节点,同时将其反转。通过快指针的最后状态判断节点数的奇偶进而调整慢指针的位置,再将前半段与后半段比较即可。

代码

Python 3.6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 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:
if head is None or head.next is None:
return True
fast, slow = head, head
last = None
while fast is not None and fast.next is not None:
slow.next, last, slow, fast = last, slow, slow.next, fast.next.next
if fast is not None:
slow = slow.next
while (slow is not None) and (last is not None) and (slow.val == last.val):
slow = slow.next
last = last.next
return slow is None

执行用时: 96 ms
内存消耗: 23.7 MB