234. 回文链表 [easy]

https://leetcode-cn.com/problems/palindrome-linked-list/

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

示例 1:

输入: 1->2
输出: false

示例 2:

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

进阶：

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

通过次数101,861 | 提交次数240,256

Second Try

2020-07-09

空间复杂度为O(1),那么无非就是继续通过快慢指针确定中间点，然后断开倒排，再依次比对。边界调节和细节要花不少时间确定和调试，其他倒还好。

# 要求空间复杂度，那又是倒排的那一套了
class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if not (head and head.next):
            return True
        slow = head 
        fast = head.next
        if not fast.next:
            return slow.val == fast.val 

        tail = head  
        while fast and fast.next:
            slow = slow.next
            tail = fast.next  
            fast = fast.next.next 
        r_head = slow.next 
        slow.next = None  # 得切断才能分为左右侧

        # print("middle", slow.val)
        # print('left', head)
        # print('right', r_head)
        # print("tail", tail)
        # tail还真不一定是最后一个，还得再找一下。。。
        if tail.next:
            tail = tail.next 
        # 倒排
        while r_head != tail:
            downstream = tail.next 
            tail.next = r_head
            r_head = r_head.next 
            tail.next.next = downstream
        # print("tail", tail)
        while head and tail:
            if head.val != tail.val:
                return False 
            head = head.next 
            tail = tail.next 
        # 在总长度为奇数的情况下，左侧会比右侧长；偶数情况下两侧一样长
        # 但好像不测试也行
        # if tail:
        #     return False 
        return True 

执行用时：60 ms, 在所有 Python 提交中击败了93.31%的用户
内存消耗：31.7 MB, 在所有 Python 提交中击败了8.33%的用户

First Try

2020-07-07

进阶版就不知道要怎么处理了，难道是先找到中间节点，然后再倒排，然后对比？如果median难道那确实应该如此。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        # 进阶版难道是先找到中间节点，然后再倒排，然后对比？

        cache = []
        while head:
            cache.append(head.val)
            head = head.next
        return cache == cache[::-1]

执行用时：72 ms, 在所有 Python 提交中击败了56.44%的用户
内存消耗：32.1 MB, 在所有 Python 提交中击败了8.33%的用户

234. 回文链表 [easy]​

Second Try​

First Try​

234. 回文链表 [easy]

Second Try

First Try