LeetCode如何判断回文链表

问题描述

回文链表是指从头到尾和从尾到头读取都是相同的链表。例如，给定链表1->2->2->1，返回true。给定链表1->2->3->2->1，返回true。给定链表1->2->3->4，返回false。

解决思路

要判断一个链表是否回文，我们可以采用如下的步骤：

1. 找到链表的中间节点。可以使用快慢指针的方式来找到链表的中间节点。快指针每次移动两步，慢指针每次移动一步，当快指针到达链表尾部时，慢指针刚好到达链表中间。
2. 将链表的后半部分反转。可以使用迭代或递归的方式来将链表的后半部分反转。
3. 比较前后两部分链表是否相同。比较反转后的后半部分链表和原始链表的前半部分是否相同，如果相同，则说明链表是回文的。
4. 恢复链表。如果需要将链表恢复成原始链表，则可以再次反转链表的后半部分，然后将其与前半部分合并。

代码示例

public boolean isPalindrome(ListNode head) {
    // 找到链表的中间节点
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    
    // 反转链表的后半部分
    ListNode prev = null;
    ListNode curr = slow;
    while (curr != null) {
        ListNode temp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = temp;
    }
    
    // 比较前后两部分链表是否相同
    ListNode p1 = head;
    ListNode p2 = prev;
    while (p1 != null && p2 != null) {
        if (p1.val != p2.val) {
            return false;
        }
        p1 = p1.next;
        p2 = p2.next;
    }
    
    // 恢复链表
    curr = prev;
    prev = null;
    while (curr != null) {
        ListNode temp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = temp;
    }
    slow.next = prev;
    
    return true;
}

以上代码中，我们通过快慢指针找到链表的中间节点，并将链表的后半部分反转。然后逐个比较前后两部分链表的节点的值是否相同，如果有不相同的节点，则链表不是回文的。最后，我们将链表恢复成原始状态。