当前位置：首页 > news >正文

力扣234题详解：回文链表的多种解法与模拟面试问答

news 来源：原创 2024/9/19 9:30:40

在本篇文章中，我们将详细解读力扣第234题“回文链表”。通过学习本篇文章，读者将掌握如何判断一个链表是否为回文链表，并了解相关的复杂度分析和模拟面试问答。每种方法都将配以详细的解释，以便于理解。

问题描述

力扣第234题“回文链表”描述如下：

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

示例:
输入: head = [1,2,2,1]
输出: true
示例:
输入: head = [1,2]
输出: false

解题思路

方法一：双指针 + 反转链表

初步分析：
- 为了判断一个链表是否是回文，我们可以利用双指针技巧找到链表的中点，然后反转链表的后半部分，最后比较前半部分和反转后的后半部分是否相同。
步骤：
- 使用快慢指针找到链表的中点。
- 反转链表的后半部分。
- 比较前半部分和反转后的后半部分是否相同。
- 最后还原链表，返回结果。

代码实现

class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextdef isPalindrome(head: ListNode) -> bool:if not head or not head.next:return True# 使用快慢指针找到链表中点slow, fast = head, headwhile fast and fast.next:slow = slow.nextfast = fast.next.next# 反转后半部分链表prev = Nonewhile slow:next_node = slow.nextslow.next = prevprev = slowslow = next_node# 比较前半部分和反转后的后半部分left, right = head, prevwhile right:if left.val != right.val:return Falseleft = left.nextright = right.nextreturn True# 测试案例
head = ListNode(1, ListNode(2, ListNode(2, ListNode(1))))
print(isPalindrome(head))  # 输出: truehead = ListNode(1, ListNode(2))
print(isPalindrome(head))  # 输出: false

方法二：利用栈

初步分析：
- 通过遍历链表将所有节点值压入栈中，然后再次遍历链表并从栈中弹出值进行比较。如果所有值都相等，则链表是回文链表。
步骤：
- 遍历链表，将节点值压入栈中。
- 再次遍历链表，从栈中弹出值并与当前节点值进行比较，如果不相等则返回 false，否则继续。
- 如果遍历完链表都相等，则返回 true。

代码实现

def isPalindrome(head: ListNode) -> bool:stack = []current = headwhile current:stack.append(current.val)current = current.nextcurrent = headwhile current:if stack.pop() != current.val:return Falsecurrent = current.nextreturn True# 测试案例
head = ListNode(1, ListNode(2, ListNode(2, ListNode(1))))
print(isPalindrome(head))  # 输出: truehead = ListNode(1, ListNode(2))
print(isPalindrome(head))  # 输出: false

复杂度分析

时间复杂度：
- 双指针 + 反转链表法：O(n)，需要遍历链表两次（找到中点和比较）。
- 利用栈的方法：O(n)，需要遍历链表两次（一次是将值压入栈，一次是比较）。
空间复杂度：
- 双指针 + 反转链表法：O(1)，只使用了少量的指针变量。
- 利用栈的方法：O(n)，需要额外的栈空间来存储链表中的值。