编写一个函数，检查输入的链表是否是回文的。
示例 1：
示例 2：
1
2
|
输入： 1->2->2->1
输出： true
|
进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
思路
1
2
3
|
1. 快慢指针遍历到链表中间，快指针走两步、慢指针走一步，最后慢指针的位置就是链表中间（画个示例图就知道了，虽然我这看的是该题的评论，不太明白，然后画了个图就了解了）
2. 从中间开始反转链表后半段
3. 从原链表头和反转后的链表头开始比较 value
|
代码
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
|
# -*- coding: utf-8 -*-
# @Time : 2020/7/15 21:27
# @Author : affectalways
# @Site :
# @Contact : affectalways@gmail.com
# @File : 0206.py
# @Software : PyCharm
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
class Solution(object):
def get_middle(self, head):
"""用快慢指针获取中间节点"""
left = right = head
while right and right.next:
left = left.next
right = right.next.next
return left
def reverse_link(self, head):
"""反转链表"""
cur = head
pre = None
while cur:
after = cur.next
cur.next = pre
pre = cur
cur = after
return pre
def isPalindrome(self, head):
"""
:type head: ListNode
:rtype: bool
"""
if head is None:
return True
# 获取中间节点
middle_node = self.get_middle(head)
# 反转链表
first = head
second = self.reverse_link(middle_node)
while second:
if first.val != second.val:
return False
first = first.next
second = second.next
return True
def create_link(tmp):
head = None
cur = head
for val in tmp:
node = ListNode(val)
if head is None:
head = node
cur = head
else:
cur.next = node
cur = cur.next
return head
def traversal_link(head):
while head:
print(head.val)
head = head.next
if __name__ == '__main__':
head = create_link([1, 1, 1, 1])
# traversal_link(head)
solution = Solution()
result = solution.isPalindrome(head)
print(result)
|
主页