讨论/《链表》 - 回文链表/
《链表》 - 回文链表

Python3

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        """
        思路:1. 找到链表的中间节点 —— 快慢指针
             2. 将后半部分链表反转
             3. 比较链表值
             4. 还原链表
        """
        if not head:
            return True
        # 1. 找到链表前半部分的尾结点
        first_half_end = self.first_half_of_end(head)
        # 2. 对链表后半部分进行反转
        second_half = self.reverse_list(first_half_end.next)
        # 3. 判断是否为回文链表
        result = True
        first_pos = head
        second_pos = second_half
        while result and second_pos is not None:
            if first_pos.val  != second_pos.val:
                return False
            first_pos = first_pos.next
            second_pos = second_pos.next
        # 4. 恢复原链表
        self.reverse_list(second_half)
        return result

    
    # 找到链表前半部分的尾结点
    def first_half_of_end(self, head):
        slow = head
        fast = head
        while fast.next is not None and fast.next.next is not None:
            slow = slow.next
            fast = fast.next.next
        return slow
    
    # 对链表进行反转
    def reverse_list(self, head):
        prev = None
        curr = head
        while curr:
            temp = curr.next
            curr.next = prev
            prev = curr
            curr = temp
        return prev
展开全部 12 讨论