回文链表的循环检测技巧

在数据结构和算法的世界中，回文链表是一个既有趣又具有挑战性的问题。这个问题要求我们判断一个链表是否是回文结构——即链表从前往后读与从后往前读的结果相同。本文将探讨如何利用循环检测机制来有效解决这一问题。

什么是回文链表？

回文链表是一种链表数据结构，其元素的排列方式使得从前向后遍历和从后向前遍历的结果完全一致。例如：1 -> 2 -> 3 -> 2 -> 1 是一个典型的回文链表，而 1 -> 2 -> 3 -> 4 不是。

题目挑战

给定一个单链表的头结点 head ，判断该链表是否为回文结构。为了简化问题处理，假设链表中的所有节点值均不相同。

解决方案：利用循环检测技巧

步骤一：使用快慢指针找到中间节点

首先，我们需要确定链表的中点位置。这可以通过使用快慢指针的方法轻松完成。具体步骤如下：

1. 初始化两个指针 slow 和 fast ，分别指向头结点。
2. 快指针每次移动两步，慢指针每次移动一步。当快指针到达链表末尾时，慢指针刚好位于中间节点。

步骤二：反转后半段链表

在找到中点后，将链表从中点断开，并反转右半部分的链表。这样可以方便地比较两部分链表是否相同。

1. 将快指针指向的下一个节点（即中间节点）设为新的头结点 new_head ，并断开连接。
2. 反转从 slow 指向的所有节点，直到 new_head 为止。

步骤三：比较前后两部分链表

反转后半段链表后，使用两个指针分别遍历前半段和后半段链表，并逐个节点进行值的比较。

1. 如果所有对应节点的值相同，则说明链表是回文结构；反之则不是。

步骤四：恢复链表

在完成上述比较后，需要将链表恢复原状。即重新连接反转后的部分到原本的位置。

示例代码

下面是一个使用 Python 实现的例子：

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

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
    curr = slow
    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node

    # 比较前后两部分链表
    right_half_head = prev
    left_half_head = head
    
    while right_half_head and left_half_head:
        if right_half_head.val != left_half_head.val:
            return False
        right_half_head = right_half_head.next
        left_half_head = left_half_head.next
    
    # 恢复链表结构
    prev = None
    curr = slow
    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node

    return True

通过上述方法，我们可以高效地检测一个给定链表是否为回文结构。这种方法不仅逻辑清晰，而且在实际应用中也能很好地满足需求。