E-234. Palindrome Linked List

Loading...LeetCode

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

# O(n), O(1)

# 1. 先找到链表的mid.
# 2. 从mid开始, 反转mid到right end的链表, 翻转后的表头为rev
# 3. 从head和rev开始, 逐一比较val, 不相等则返回False

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        slow, fast = head, head
        # find mid:
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        
        rev = None
        # reverse right half:
        while slow:
            nxt = slow.next
            slow.next = rev
            rev = slow
            slow = nxt
        
        # compare from head and tail(rev)
        # 注意, 退出的时候, head指向rev的最后一个非空节点, rev指向None(即最后
        # 一个非空节点的next).
        # 画图可以搞明白
        while rev:
            if head.val != rev.val:
                return False
            else:
                head = head.next
                rev = rev.next
        return True

# 改了两行, 可以和上面对比一下
class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        slow, fast = head, head
        # find mid:
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        
        # 改了这里
        rev = ListNode(None)
        # reverse right half:
        while slow:
            nxt = slow.next
            slow.next = rev
            rev = slow
            slow = nxt
        
        # compare from head and tail(rev)
        # 改了这里
        while rev.next:
            if head.val != rev.val:
                return False
            else:
                head = head.next
                rev = rev.next
        return True