[LeetCode] 234. Palindrome Linked List_Easy tag: Linked List

佚名 6年前 (2019-05-06) 随笔 1290人围观抢沙发百度已收录

Given a singly linked list, determine if it is a palindrome.

Example 1:

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

Input: 1->2
Output: false

Example 2:

Input: 1->2->2->1
Output: true

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

这个题目就是先找中点，然后将中点后的list都reverse，进而分别将每个点比较，一旦不等，那么返回False，最后返回True。

T: O(n), S: O(1)

code

# 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 not head or not head.next: return True
        dummy = ListNode(0)
        dummy.next = head
        slow, fast = dummy, dummy
        while fast:
            if not fast.next:
                break
            if not fast.next.next:
                fast.next = fast.next.next
            slow = slow.next
            fast = fast.next.next
        pre, cur, count = slow, slow.next, 0
        while cur:
            count += 1
            temp = cur.next
            cur.next = pre
            pre = cur
            cur = temp
        # compare two lists
        for _ in range(count):
            if pre.val != head.val:
                return False
            pre = pre.next
            head = head.next
        return True