题目
难度：★★☆☆☆
类型：链表
请判断一个链表是否为回文链表。
进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
示例
示例 1:
输入: 1->2
输出: false
示例 2:
输入: 1->2->2->1
输出: true
解答
方案1：逆序链表
这道题目【题目9. 回文数】和【题目125. 验证回文串】都属于回文类型的判别题，我们首先考虑将链表进行逆序，判断逆序后的链表与原链表是否相等。
链表的数据结构特殊，需要有以下注意：
链表的逆序过程可能会改变原链表的结构，因此我们定义了一个函数（copy_linked_list）用于实现链表的浅拷贝，防止链表输入逆序函数后结构被改变的情况出现；
链表的相等判断需要对链表中每个相应位置的元素值进行判断，而不能仅仅对链表整体进行判断，这里我们定义了函数（list_equal）用于判断两个链表是否相等。
class Solution(object):
def isPalindrome(self, head):
"""
:type head: ListNode
:rtype: bool
"""
def copy_linked_list(head):
"""
把链表复制一份，且不改变原链表结构
:param head:
:return:
"""
new_head, cur = ListNode(0), head # 新链表的准头结点，原来链表的当前结点
tmp = new_head # 临时结点
while cur: # 当前结点不为空
new_cur = ListNode(cur.val) # 根据原链表当前结点构造新的当前结点
tmp.next = new_cur # 新结点连接到已完成的部分末尾
cur = cur.next # 当前结点后移
tmp = tmp.next # 新链表末尾后移
return new_head.next # 返回新链表
def reverse_linked_list(head):
"""
将链表逆序，这里用递归实现
:param head:
:return:
"""
if not head or not head.next:
return head
p = reverse_linked_list(head.next)
head.next.next = head
head.next = None
return p
def list_equal(head1, head2):
"""
判断两个链表是否相等
:param head1:
:param head2:
:return:
"""
while head1 and head2: # 逐一比较
if head1.val != head2.val:
return False
head1, head2 = head1.next, head2.next
return not head1 and not head2
reversed_head = reverse_linked_list(copy_linked_list(head)) # 链表逆序
return list_equal(reversed_head, head) # 判断逆序后的链表与原链表当前是否相等
方案2：利用栈
我们可以首先统计链表中元素的个数，然后从头开始再次遍历链表，同时将当前结点入栈，遍历到链表中点位置后，后半段链表不再入栈，栈中的元素依次出栈并与当前结点进行比对，直到链表末尾，中途有任意结点不匹配则不是回文链表。这里需要注意链表长度为奇数和偶数时的区别问题。
class Solution(object):
def isPalindrome(self, head):
"""
:type head: ListNode
:rtype: bool
"""
def get_linked_list_length(head):
"""
获得链表长度
:param head:
:return:
"""
tmp = head # 为了不影响输入链表的结构，使用临时变量
if not tmp:
return 0
count = 1
while tmp and tmp.next:
count += 1
tmp = tmp.next
return count
length = get_linked_list_length(head) # 获得链表长度
stack = [] # 定义一个栈
tmp = head # 定义临时结点，为了不改变输入的结构
count = 0 # 计数器初始化为零
while count < length // 2: # 对前一半链表进行处理
stack.append(tmp.val) # 当前结点入栈
tmp = tmp.next # 当前结点后移
count += 1 # 计数器+1
if length % 2 == 1: # 奇数长度链表
tmp = tmp.next # 跳过最中间的结点
while tmp: # 只要没有到达链表末尾
cur = stack.pop() # 弹出栈顶元素
if cur != tmp.val: # 比较当前结点的值和栈顶元素是否相等
return False # 如果不等，一定不是回文链表
tmp = tmp.next # 继续遍历
return True # 如果通过了所有的测试，则返回True
方案3：快慢指针
我们定义一个快指针和一个慢指针，每次分别走两步和一步，当快指针到达链表末尾时，慢指针到达链表中间，这时，我们将慢指针之后的一半链表逆序，比较左右两段链表是否相等。这里同样需要注意链表长度奇偶问题。
class Solution(object):
def isPalindrome(self, head):
"""
:type head: ListNode
:return: bool
"""
def reverse_list(root):
"""
链表逆序
:param root:
:return:
"""
pre = None
cur = root
while cur:
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
return pre
def list_equal_former(head1, head2):
"""
判断两个链表前几个元素是否相等，是否存在包含关系
:param head1:
:param head2:
:return:
"""
tmp1, tmp2 = head1, head2
while tmp1 and tmp2: # 逐一比较
if tmp1.val != tmp2.val:
return False
tmp1, tmp2 = tmp1.next, tmp2.next
# return not head1 and not head2 # 如果判断两个链表是否相等，应该返回这个
return True
slow = fast = head # 快慢指针找中点
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return list_equal_former(head, reverse_list(slow))
如有疑问或建议，欢迎评论区留言~
