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

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

article 2024/9/21 20:39:13

在本篇文章中，我们将详细解读力扣第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 = val
        self.next = next

def isPalindrome(head: ListNode) -> bool:
    if not head or not head.next:
        return True
    
    # 使用快慢指针找到链表中点
    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    
    # 反转后半部分链表
    prev = None
    while slow:
        next_node = slow.next
        slow.next = prev
        prev = slow
        slow = next_node
    
    # 比较前半部分和反转后的后半部分
    left, right = head, prev
    while right:
        if left.val != right.val:
            return False
        left = left.next
        right = right.next
    
    return True

# 测试案例
head = ListNode(1, ListNode(2, ListNode(2, ListNode(1))))
print(isPalindrome(head))  # 输出: true

head = ListNode(1, ListNode(2))
print(isPalindrome(head))  # 输出: false

方法二：利用栈

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

代码实现

def isPalindrome(head: ListNode) -> bool:
    stack = []
    current = head
    
    while current:
        stack.append(current.val)
        current = current.next
    
    current = head
    while current:
        if stack.pop() != current.val:
            return False
        current = current.next
    
    return True

# 测试案例
head = ListNode(1, ListNode(2, ListNode(2, ListNode(1))))
print(isPalindrome(head))  # 输出: true

head = ListNode(1, ListNode(2))
print(isPalindrome(head))  # 输出: false

复杂度分析

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