leetcode with python:234. Palindrome Linked List

题目:

Given the head of a singly linked list, return true if it is a palindrome.

给定一个linked list,判断它是否对称

这题我并没有什么头绪,于是採取了最笨的做法

# Definition for singly-linked list.# class ListNode:#     def __init__(self, val=0, next=None):#         self.val = val#         self.next = nextclass Solution:    def isPalindrome(self, head: Optional[ListNode]) -> bool:        record=[]        while head:            record.append(head.val)            head=head.next                for i in range(len(record)//2):            if record[i]!=record[-1-i]:                return False                    return True

将linked list所有值纪录到阵列内
再前后比较阵列值是否相等来决定该linked list是否对称
虽然阳春,但效率不会到太差
最后执行时间784ms(faster than 95.31%)

当然这种解法是不能瞒混过关的
题目随即说了一句

Follow up: Could you do it in O(n) time and O(1) space?

想不到不用额外空间解的我只好去看讨论区
结果就看到了下面的解法

# Definition for singly-linked list.# class ListNode:#     def __init__(self, val=0, next=None):#         self.val = val#         self.next = nextclass Solution:    def isPalindrome(self, head: Optional[ListNode]) -> bool:        fast=head        slow=head        while fast and fast.next:            fast=fast.next.next            slow=slow.next                    pre=None        while slow:            temp=slow.next            slow.next=pre            pre=slow            slow=temp                    l=head        r=pre        while r:            if l.val!=r.val:                return False            l=l.next            r=r.next        return True

设立fast跟slow两个指标,一个一次走两步,一个一次走一步
直到fast走到底为止
此时可以发现slow会在linked list近中央的位置
将slow之后的linked list全数反转(pre刚好会是反转后的头)
这时我们只要一个指标从head开始,一个指标从pre开始
就能比较值来决定该linked list是否对称了
最后执行时间796ms(faster than 94.00%)

那我们下题见