提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

【数组&双指针】leetcode 234. 回文链表【简单】

ampLeetCode链表数组 简单 指针 回文 234
2023-09-14 09:01:22 时间

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

示例 1：

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

示例2:

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

提示：

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

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

【分析】

这道题有很多种解法：

1、反转链表，再和原链表各元素按顺序对比；

2、将链表各节点元素加入数组，再利用左右指针向中间同时滑动，判断左右指针位置处的值是否相等；

3、递归法，后序遍历链表，判断倒序的节点值和正序的节点值是否相同；

4、快慢指针先找到链表的中间位置，将后半段链表反转，再按顺序对比各元素是否相同，最终恢复原链表（再进行一次反转）

前三种方法的时空复杂度都是O(n)，第四种方法的时间复杂度为O(n)，空间复杂度为O(1)，因此第四种方法满足题目最终的要求。

【方法一】：将链表元素复制到数组中，使用双指针。

一些概念：有两种常用的列表实现，分别为数组列表和链表。如果我们想在列表中存储值，它们是如何实现的呢？

（1）数组列表底层是使用数组存储值，我们可以通过索引在O(1)的时间访问列表任何位置的值，这是由基于内存寻址的方式；　

（2）链表存储的是称为节点的对象，每个节点保存一个值和指向下一个节点的指针。访问某个特定索引的节点需要O(n)的时间，因为要通过指针获取到下一个位置的节点。

确定数组列表是否回文很简单，我们可以使用双指针法来比较两端的元素，并向中间移动。这需要O(n)的时间，因为访问每个元素的时间是O(1)，而有n个元素要访问。

然而同样的方法在链表上操作并不简单，因为不论是正向访问还是反向访问都不是O(1)。而将链表的值复制到数组列表中是O(n)，因此最简单的方法就是将链表的值复制到数组列表中，再使用双指针法来判断。

算法分为两步：复制链表值到数组列表中；使用双指针法判断是否为回文。

第一步，我们需要遍历链表将值复制到数组中。我们用currentNode指向当前节点。每次迭代向数组添加current Node.val，并更新currentNode = currentNode.next，当currentNode = null的时候停止循环。

第二步，执行这一步的最佳方法取决于你使用的语言，在python中，很容易构造一个列表反向副本，也很容易比较两个列表。而在其他语言中，就没有那么简单。因此最好使用双指针法来检查是否为回文。我们在起点放置一个指针，在结尾放置一个指针，每一次迭代判断两个指针指向的元素是否相同，若不同，返回false，否则将两个指针向内移动，并继续判断，直到两个指针相遇。

在编码过程中，注意我们比较的是节点值的大小，而不是节点本身。正确的比较方式是：node_1.val == node_2.val，而 node_1 == node_2 是错误的。

时空复杂度：O(n)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        vals = []
        current_node = head
        while current_node is not None:
            vals.append(current_node.val)
            current_node = current_node.next
        return vals == vals[::-1]

【方法二】：递归

为了想出使用空间复杂度为O(1)的算法，你可能想过使用递归来解决，但是这仍然需要O(n)的空间复杂度。

递归为我们提供了一种优雅的方式来遍历节点。

function print_values_in_reverse(ListNode head)
    if head is NOT null
        print_values_in_reverse(head.next)
        print head.val

如果使用递归反向迭代节点，同时使用递归函数外的变量向前迭代，就可以判断链表是否为回文。

算法：currentNode指针是先到尾节点，再基于递归特性，从后往前进行比较。frontPointer是递归函数外的指针。若

currentNode.val != frontPointer.val则返回false。反之，frontPointer向前移动并返回true。

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

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
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
                if self.front_pointer.val != current_node.val:
                    return False
                self.front_pointer = self.front_pointer.next
            return True
        
        return recursively_check()

# 复杂度分析
# 时间复杂度：O(n)O(n)，其中 nn 指的是链表的大小。
# 空间复杂度：O(n)O(n)，其中 nn 指的是链表的大小。
我们要理解计算机如何运行递归函数，在一个函数中调用一个函数时，
计算机需要在进入被调用函数之前跟踪它在当前函数中的位置（以及任何局部变量的值），
通过运行时存放在堆栈中来实现（堆栈帧）。在堆栈中存放好了数据后就可以进入被调用的函数。
在完成被调用函数之后，他会弹出堆栈顶部元素，以恢复在进行函数调用之前所在的函数。
在进行回文检查之前，递归函数将在堆栈中创建 nn 个堆栈帧，计算机会逐个弹出进行处理。
所以在使用递归时空间复杂度要考虑堆栈的使用情况。

【方法三：快慢指针】

避免使用O(n)额外空间的方法就是改变输入。

我们可以将链表的后半部分反转（修改链表结构），然后将前半部分和后半部分进行比较。比较完成后我们应该将链表恢复原样。虽然不需要恢复也能通过测试用例，但使用该函数的人通常不希望链表结构被改。

该方法虽然可以将空间复杂度降到O(1)，但是在并发环境下也有缺点，就是函数运行时需要锁定其他线程或进程对链表的访问，因为在函数执行过程中链表会被修改。

算法流程：

（1）找到前半部分链表的尾节点

（2）反转后半部分链表

（3）判断是否回文

（4）恢复链表

（5）返回结果

执行步骤一，我们可以计算链表节点的数量，然后遍历链表找到前半部分的尾节点。

也可以使用快慢指针在一次遍历中找到：慢指针一次走一步，快指针一次走两步，快慢指针同时出发。当快指针移动到链表末尾时，慢指针恰好到链表的中间。通过慢指针将链表分为两部分。

若链表有奇数个节点，则中间的节点应该被视为前半部分。

步骤二可以使用「206. 反转链表」问题中的解决办法来反转链表的后半部分。

步骤三比较两部分的值，当后半部分到达末尾则比较工作完成，可以忽略计数情况中的中间节点。

步骤四和步骤二使用的函数相同，再反转一次恢复链表本身。

class Solution:

    def isPalindrome(self, head: ListNode) -> bool:
        if head is None:
            return True

        # 找到前半部分链表的尾节点并反转后半部分链表
        first_half_end = self.end_of_first_half(head)
        second_half_start = self.reverse_list(first_half_end.next)

        # 判断是否回文
        result = True
        first_position = head
        second_position = second_half_start
        while result and second_position is not None:
            if first_position.val != second_position.val:
                result = False
            first_position = first_position.next
            second_position = second_position.next

        # 还原链表并返回结果
        first_half_end.next = self.reverse_list(second_half_start)
        return result    

    def end_of_first_half(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

    def reverse_list(self, head):
        previous = None
        current = head
        while current is not None:
            next_node = current.next
            current.next = previous
            previous = current
            current = next_node
        return previous


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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

相关文章