【Leetcode链表】回文链表（234）

题目

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

示例 1:

输入: 1->2

输出: false

示例 2:

输入: 1->2->2->1

输出: true

进阶：

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

解答

两种方法：

遍历链表，用数组存值，再比较。时间复杂度O(n)，空间复杂度O(n)
指针法：找到中点，反转中点之后的链表，再比较。时间复杂度O(n)，空间复杂度O(1)

通过代码如下：

# Definition for singly-linked list.

# class ListNode:

#     def __init__(self, x):

#         self.val = x

#         self.next = None

from math import *

class Solution:

    # # 改为数组：时间复杂度O(n)，空间复杂度O(n)

    # def isPalindrome(self, head: ListNode) -> bool:

    #     l = []

    #     while head:

    #         l.append(head.val)

    #         head = head.next

    #     return l == l[::-1]

    # 指针法：时间复杂度O(n)，空间复杂度O(1)。找到中点，反转中点之后的链表，再比较

    def isPalindrome(self, head: ListNode) -> bool:

        if not head or not head.next:

            return True

        # 找到中点，快指针走的路程是慢的两倍，快指针结束慢指针刚好在中间

        f = s = head

        while f:

            s = s.next

            f = f.next.next if f.next else f.next

        # 反转中点之后的链表，1->2->0->2->1 ————》 1->2->0<-2<-1

        c, p = s, None

        while c:

            n = c.next

            c.next = p

            p = c

            c = n

        # 相对比较

        while p:

            if head.val != p.val:

                return False

            head = head.next

            p = p.next

        return True

巴特西

【Leetcode链表】回文链表（234）

题目

解答

最新文章

热门文章