题目链接

判断一个链表是否为回文结构

题目描述

给定一个单链表，请判断该链表是否为回文结构。回文是指一个序列正序和逆序完全一致。

数据范围: 链表节点数 。 这是一个核心代码模式的题目，你只需要实现 isPail 函数即可。

示例:

  • 输入: {1,2,2,1}

  • 输出: true

  • 输入: {1,2,3,2,1}

  • 输出: true

  • 输入: {1,2,3,4,5}

  • 输出: false

解题思路

判断链表是否为回文结构，关键在于如何"从后往前"读取链表的值。

方法一：栈或数组 (空间复杂度 )

最直观的方法是将链表的值全部存入一个额外的数据结构中，比如栈或数组。

  • 使用数组：遍历链表，将所有值存入数组。然后用双指针法判断该数组是否为回文。
  • 使用栈：遍历链表，将所有节点依次入栈。然后再次从头遍历链表，每遍历一个节点，就从栈中弹出一个节点进行比较。 这两种方法都很简单，但都需要 的额外空间。

方法二：快慢指针 + 反转链表 (空间复杂度 )

这是本题的最优解，可以在不使用额外空间的情况下完成判断。

算法步骤:

  1. 找到链表的前半部分的末尾节点：

    • 使用快慢指针法。slow 指针一次走一步，fast 指针一次走两步。
    • 当 fast 指针到达链表末尾时（fast.next == null 或 fast.next.next == null），slow 指针正好指向前半部分的最后一个节点。
    • 例如，对于 1->2->3->2->1，slow 会停在 2。对于 1->2->2->1，slow 会停在第一个 2。

  2. 反转后半部分的链表：

    • 从 slow.next 开始，将链表的后半部分进行反转。
    • 例如，1->2->3->2->1 会变成 1->2->3 和 1->2 (反转 2->1 得到)。
    • 1->2->2->1 会变成 1->2 和 1->2 (反转 2->1 得到)。

  3. 比较前后两半：

    • 设置两个指针，一个指向链表头 head，另一个指向反转后的后半部分的头。
    • 同步向后移动这两个指针，并比较对应节点的值。
    • 如果出现任何不匹配，说明链表不是回文，返回 false。

  4. 返回结果：

    • 如果比较完整个后半部分都没有发现不匹配，说明链表是回文，返回 true。

  5. (可选) 恢复链表: 为了不破坏原始链表的结构，可以在比较完成后，再次反转后半部分链表，并将其重新连接到前半部分。

这个方法巧妙地将问题分解为三个子问题：找中点、反转链表和比较链表，都是链表操作的基本功。

代码

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    bool isPail(ListNode* head) {
        if (head == nullptr) {
            return true;
        }

        // 1. 找到前半部分的尾部
        ListNode* firstHalfEnd = findFirstHalfEnd(head);
        // 2. 反转后半部分
        ListNode* secondHalfStart = reverseList(firstHalfEnd->next);

        // 3. 判断是否为回文
        ListNode* p1 = head;
        ListNode* p2 = secondHalfStart;
        bool result = true;
        while (result && p2 != nullptr) {
            if (p1->val != p2->val) {
                result = false;
            }
            p1 = p1->next;
            p2 = p2->next;
        }

        // 4. 恢复链表（可选，但好习惯）
        firstHalfEnd->next = reverseList(secondHalfStart);
        
        return result;
    }

private:
    ListNode* findFirstHalfEnd(ListNode* head) {
        ListNode* fast = head;
        ListNode* slow = head;
        while (fast->next != nullptr && fast->next->next != nullptr) {
            fast = fast->next->next;
            slow = slow->next;
        }
        return slow;
    }

    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr != nullptr) {
            ListNode* nextTemp = curr->next;
            curr->next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }
};

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    public boolean isPail(ListNode head) {
        if (head == null) {
            return true;
        }

        // 1. 找到前半部分的尾部
        ListNode firstHalfEnd = findFirstHalfEnd(head);
        // 2. 反转后半部分
        ListNode secondHalfStart = reverseList(firstHalfEnd.next);

        // 3. 判断是否为回文
        ListNode p1 = head;
        ListNode p2 = secondHalfStart;
        boolean result = true;
        while (result && p2 != null) {
            if (p1.val != p2.val) {
                result = false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }

        // 4. 恢复链表（可选）
        firstHalfEnd.next = reverseList(secondHalfStart);

        return result;
    }

    private ListNode findFirstHalfEnd(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = curr.next; // 注意这里是 curr = nextTemp
            curr = nextTemp;
        }
        return prev;
    }
}

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# @param head ListNode类 the head
# @return bool布尔型
#
class Solution:
    def isPail(self, head: ListNode) -> bool:
        if not head:
            return True

        # 1. 找到前半部分的尾部
        first_half_end = self.find_first_half_end(head)
        # 2. 反转后半部分
        second_half_start = self.reverse_list(first_half_end.next)

        # 3. 判断是否为回文
        p1 = head
        p2 = second_half_start
        result = True
        while result and p2:
            if p1.val != p2.val:
                result = False
            p1 = p1.next
            p2 = p2.next

        # 4. 恢复链表（可选）
        first_half_end.next = self.reverse_list(second_half_start)

        return result

    def find_first_half_end(self, head: ListNode) -> ListNode:
        fast = head
        slow = head
        while fast.next and fast.next.next:
            fast = fast.next.next
            slow = slow.next
        return slow

    def reverse_list(self, head: ListNode) -> ListNode:
        prev = None
        curr = head
        while curr:
            next_temp = curr.next
            curr.next = prev
            prev = curr
            curr = next_temp
        return prev

算法及复杂度

  • 算法: 快慢指针 + 反转链表
  • 时间复杂度: 。其中 是链表的节点数。找中点、反转、比较和恢复，每一步都大致需要 的时间，所以总体是 。
  • 空间复杂度: 。我们只使用了常数个额外的指针变量。