回文链表的经典面试题讲解

引言

在编程面试中，回文结构是一个常见的主题。其中，回文链表是指一个链表从前往后读和从后往前读完全相同。这个问题不仅考察了算法设计能力，还考验了解决问题的创新思维。接下来，我们将详细探讨如何解决“检查链表是否为回文”这一经典面试题。

问题描述

给定一个单向链表，编写一个函数判断这个链表是否是一个回文结构。输入是一个带有头节点的链表，输出是一个布尔值表示该链表是否为回文。

示例

输入

head = [1, 2, 3, 2, 1]

输出

True

输入

head = [1, 2, 3, 4, 5]

输出

False

解题思路

解决此问题的关键在于如何比较链表中的数据，使其能够前后对称。主要可以分为以下几种方法：

方法一：使用栈

通过将链表节点值压入栈中，然后弹出并与链表当前节点的值进行对比。

1. 初始化：

   • 使用一个指针遍历整个链表。
   • 使用一个栈来存储遍历过程中遇到的所有节点值。

2. 遍历并存入栈：

   • 遍历链表，将每个节点值依次压入栈中。

3. 比较回文性：

   • 重新遍历链表（或从栈中弹出元素），与栈中的元素进行对比。
   • 如果有任何不匹配，则返回 False；否则最终返回 True。

方法二：快慢指针 + 反转后半部分

1. 初始化：

   • 使用两个指针，一个移动速度快（快指针），另一个移动速度慢（慢指针）。

2. 找到链表中点：

   • 快慢指针同时遍历链表。当快指针到达尾部时，慢指针正好位于链表中间。

3. 反转后半部分链表：

   • 反转从慢指针对应的节点开始到链表末尾的部分。

4. 逐个对比值：

   • 从前半段和反转后的后半段同时进行遍历，检查对应位置的元素是否相等。
   • 如果所有对应位置元素均匹配，则链表为回文结构；否则不是。

5. 恢复原状（可选）：

   • 根据面试要求选择是否需要恢复链表结构（如需则执行步骤6-7，否则直接返回结果即可）。

6. 反转后半部分重新归位：

   • 为了保持链表不变，可以将前半段和后半段再还原。

7. 返回结果

实现代码

以下是使用快慢指针方法的 Python 代码实现：

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def is_palindrome(head: ListNode) -> bool:
    if not head or not head.next:
        return True
    
    # Find the middle of the linked list
    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    
    # Reverse the second half of the list
    prev = None
    current = slow
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    
    # Check if the first and second halves are equal
    first_half = head
    second_half = prev
    is_palindromic = True
    
    while second_half:
        if first_half.val != second_half.val:
            is_palindromic = False
            break
        first_half = first_half.next
        second_half = second_half.next
    
    # Restore the original linked list (optional)
    current = prev
    while current and current.next:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    
    return is_palindromic

# 示例用法
node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node4 = ListNode(2)
node5 = ListNode(1)

node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5

print(is_palindrome(node1))  # 输出: True

总结

解决回文链表问题的关键在于如何有效地比较链表前后半段的元素，这里我们分别使用了栈和快慢指针反转部分链表的方法。这两种方法各有优缺点，选择哪种取决于具体需求和实现难度考虑。在实际面试中，清晰地阐述你的解题思路以及所选方法的优点是极其重要的。