leetcode 好题笔记 —— [234] 回文链表

CK...大约 4 分钟

leetcode 好题笔记 —— [234] 回文链表

题目描述

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例1:

输入：head = [1,2,2,1]
输出：true

示例2:

输入：head = [1,2]
输出：false

提示:

链表中节点数目在范围[1, 105] 内
0 <= Node.val <= 9

实现算法

一、快慢指针

所谓快慢指针，是寻找链表中间节点的有效方法。也可用于判断链表回路是否存在环。

快慢指针算法思想:

定义快慢指针fast和slow，起始均位于链表头部。规定fast每次后移2步，slow后移1步；
若fast遇到null节点，则表示链表无环，结束；

此时slow点所在节点即为链表的中心节点，奇数链表返回中间值，偶数列表返回中间偏前值。

若链中有环，fast和slow一定会再次相遇；
当fast和slow相遇时，额外创建指针ptr，并指向链表头部，且每次后移1步，最终slow和ptr会在入环点相遇。

实现代码：

    def helfListNode_of_list(self, head):
        # 快慢指针返回中间指针
        fast = head
        slow = head
        while fast.next is not None and fast.next.next is not None:
            fast = fast.next.next
            slow = slow.next
        #! 奇数链表返回中间值,偶数列表返回中间偏前值
        return slow

2. 递归反转链表

这里的递归比较难理解，为了翻转链表，首先使用递归找到最后一个节点，在下文的实现代码中，我将其定义为 head_next ，而遍历到此时的 head 的节点即为最后节点 head_next 的父节点，即倒数第二个节点

    # 子节点指向父节点，并切断父节点指向子节点
    head.next.next = head
    head.next = None

以此递归回去，使每一个节点都指向父节点，而切断原父节点对子节点的指向。需要注意的是，我们在此过程中并未对最后节点 head_next 进行任何操作，所以最终返回的便是翻转后的链表头结点。

实现代码：

    def reserve_list(self, head:ListNode) -> ListNode:
        #! 返回翻转链表头结点
        if head is None or head.next is None:
            return head
        else:
            # head_next 为最后一个节点,此步骤为了找到最后一个节点
            head_next = self.reserve_list(head.next)
        # 子节点指向父节点
        head.next.next = head
        head.next = None
        return head_next

3. 总接口函数

目的操作： 找到前半部分链表的尾节点并反转后半部分链表，对两串列表进行一一对应操作以此判断链表是否为回文链表。

实现代码：

class Solution:    
    def isPalindrome(self, head: ListNode) -> bool:
        if head is None or head.next is None:
            return True
        mid_node = self.helfListNode_of_list(head)
        reserved_head = self.reserve_list(mid_node.next)
        
        while reserved_head is not None:
            if head.val != reserved_head.val:
                return False
            else:
                head = head.next
                reserved_head = reserved_head.next
        
        return True

复杂度分析

时间复杂度：O(n) ，其中 n 指的是链表的大小。
空间复杂度：O(1) 。我们只会修改原本链表中节点的指向，而在堆栈上的堆栈帧不超过 O(1)

二、递归

算法思想： currentNode 指针是先到尾节点，由于递归的特性再从后往前进行比较。frontPointer 是递归函数外的指针。若 currentNode.val != frontPointer.val 则返回 false。反之，frontPointer 向前移动并返回 true。

算法的正确性在于递归处理节点的顺序是相反的（回顾上面打印的算法），而我们在函数外又记录了一个变量，因此从本质上，我们同时在正向和逆向迭代匹配。

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

        self.front_pointer = head

        def recursively_check(current_node=head):
            if current_node is not None:
                # 不断递归的目的是找到最后一个节点
                if not recursively_check(current_node.next):
                    return False
                # front_pointer 从头开始 current_node 递归从尾开始
                if self.front_pointer.val != current_node.val:
                    return False
                self.front_pointer = self.front_pointer.next
            return True

        return recursively_check()

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/palindrome-linked-list/solution/hui-wen-lian-biao-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

复杂度分析

时间复杂度：O(n) ，其中 n 指的是链表的大小。
空间复杂度：O(n) ，其中 n 指的是链表的大小。