程序员面试金典 - 面试题 02.06. 回文链表

题目难度: 简单

原题链接

今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~

题目描述

编写一个函数，检查输入的链表是否是回文的。

示例 1：

• 输入： 1->2
• 输出： false

示例 2：

• 输入： 1->2->2->1
• 输出： true

题目思考

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

解决方案

思路

• 相比传统的数组或者字符串求回文, 链表不能直接取下标, 也无法像双向链表那样用双指针往中间靠拢比较的方法, 如何做到 O(n) 时间复杂度和 O(1) 空间复杂度呢?
• 分析双指针往中间靠拢比较的原理, 它是第一个和最后一个比较, 第二个和倒数第二个比较, 以此类推...
• 所以我们可以人为将链表分成左右两半部分, 然后将右半部分进行反转, 再用双指针从两部分的头节点依次往后比较即可
• 这样就把问题分解成了 3 个经典的小问题, 它们都可以利用双指针来解决, 大家可以结合下面的代码和注释进行理解
• 如果题目要求恢复原来链表结构的话, 还可以将链表翻转部分提取出来, 然后比较完之后再将右半部分转回去, 下面代码也实现了这一步

复杂度

• 时间复杂度 O(N): 只需要遍历每个节点三遍(划分/翻转/比较)
• 空间复杂度 O(1): 只使用了几个常数空间的变量

代码

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        # 把右半部分翻转后再双指针依次比较, 最后将输入链表结构恢复成原样
        # 第一步: 使用快慢指针找中点
        fast = head
        slow = head
        while fast:
            fast = fast.next
            if fast:
                fast = fast.next
            slow = slow.next
        # 此时slow就是右半部分的头节点(左半部分长度可能相等或多1, 对应总长度是偶数和奇数的情况)
        # 第二步: 定义翻转函数, 将右半部分进行翻转
        def reverse(cur):
            # 翻转并返回新的头
            pre = None
            while cur:
                nex = cur.next
                cur.next = pre
                pre, cur = cur, nex
            return pre

        # 第三步: 双指针依次比较左右两部分对应节点, 并记录右半部分末尾节点用于恢复原始结构
        left, right = head, reverse(slow)
        rightTail = right
        res = True
        while left and right:
            if left.val != right.val:
                res = False
                break
            left = left.next
            rightTail = right
            right = right.next
        # 得到右半部分末尾节点并翻转恢复(注意它可能不存在, 如果当原始链表长度小于等于1时)
        while rightTail and rightTail.next:
            rightTail = rightTail.next
        reverse(rightTail)
        return res

大家可以在下面这些地方找到我~😊

我的知乎专栏

我的头条号

我的 CSDN

我的 Leetcode

我的牛客网博客

我的公众号: 算法精选, 欢迎大家扫码关注~😊