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

LeetCode题练习与总结：回文链表--234

article 2024/11/12 4:22:54

一、题目描述

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：

输入：head = [1,2,2,1]
输出：true

示例 2：

输入：head = [1,2]
输出：false

提示：

链表中节点数目在范围[1, 10^5] 内
0 <= Node.val <= 9

二、解题思路

快慢指针法找到链表中点：我们可以使用两个指针，快指针每次移动两步，慢指针每次移动一步。当快指针到达链表末尾时，慢指针恰好到达链表中点。
翻转后半部分链表：当找到链表中点后，我们可以将后半部分链表翻转，以便与前半部分链表进行比较。
比较前后两部分链表：将前半部分链表与翻转后的后半部分链表进行比较，如果每个节点的值都相等，则为回文链表。
恢复链表（可选）：如果题目要求不改变原链表结构，我们需要在比较完成后，将后半部分链表再次翻转回来。

三、具体代码

class Solution {
    public boolean isPalindrome(ListNode head) {
        // 快慢指针找到链表中点
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        // 如果链表长度为奇数，慢指针需要再向前移动一位
        if (fast != null) {
            slow = slow.next;
        }
        
        // 翻转后半部分链表
        ListNode prev = null;
        ListNode curr = slow;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        
        // 比较前后两部分链表
        ListNode firstHalf = head;
        ListNode secondHalf = prev;
        while (secondHalf != null) {
            if (firstHalf.val != secondHalf.val) {
                return false;
            }
            firstHalf = firstHalf.next;
            secondHalf = secondHalf.next;
        }
        
        return true;
    }
}

注意：在比较完成后，如果题目没有要求恢复原链表结构，则不需要再次翻转后半部分链表。如果需要恢复，可以在比较完成后，将上述翻转后半部分链表的代码再执行一遍。

四、时间复杂度和空间复杂度

1. 时间复杂度

快慢指针遍历链表：这个步骤中，快指针每次移动两步，慢指针每次移动一步，直到快指针到达链表末尾。在最坏的情况下，快指针会遍历整个链表一次，而链表长度为 n，所以时间复杂度为 O(n)。
翻转后半部分链表：这个步骤中，我们需要遍历链表的后半部分，也就是大约 n/2 个节点，因此时间复杂度为 O(n/2)，这可以简化为 O(n)。
比较前后两部分链表：在这个步骤中，我们比较前后两部分链表，每部分大约有 n/2 个节点，因此时间复杂度为 O(n/2)，这同样可以简化为 O(n)。

将上述步骤的时间复杂度相加，我们得到总的时间复杂度为 O(n) + O(n) + O(n) = O(n)。

2. 空间复杂度

快慢指针遍历链表：这个步骤中，我们只使用了常数个额外空间（即快慢指针），因此空间复杂度为 O(1)。
翻转后半部分链表：在这个步骤中，我们没有使用额外的数据结构，而是直接在原链表上进行操作，所以空间复杂度仍然是 O(1)。
比较前后两部分链表：这个步骤中，我们也没有使用额外的空间，只是通过指针遍历链表，所以空间复杂度为 O(1)。

将上述步骤的空间复杂度相加，我们得到总的空间复杂度为 O(1) + O(1) + O(1) = O(1)。

综上所述，该算法的时间复杂度为 O(n)，空间复杂度为 O(1)。

五、总结知识点

链表（Linked List）：
- 链表是一种常见的基础数据结构，由一系列节点组成，每个节点包含数据域和指向下一个节点的指针。
单链表（Singly Linked List）：
- 代码中的链表是单链表，每个节点只包含一个指向下一个节点的指针。
快慢指针（Fast and Slow Pointers）：
- 快慢指针是一种技巧，常用于解决链表中的问题，如查找链表中点、检测环等。快指针每次移动两步，慢指针每次移动一步。
链表翻转（Reversing a Linked List）：
- 代码展示了如何通过迭代的方式翻转链表的一部分。这是通过改变节点指针的方向来实现的。
递归（Recursion）：
- 虽然代码中没有直接使用递归，但翻转链表的过程也可以通过递归来实现。
迭代（Iteration）：
- 代码中使用了迭代（循环）来翻转链表的后半部分以及比较链表的前后两部分。
边界条件处理：
- 在快慢指针寻找中点的过程中，代码处理了链表长度为奇数的情况，确保慢指针正确地指向后半部分链表的第一个节点。
逻辑判断（Logical Comparison）：
- 代码中使用了 if 语句来比较链表前后两部分节点的值，以判断链表是否为回文。
链表节点类定义（ListNode Class Definition）：
- 虽然代码片段中没有给出 ListNode 类的定义，但它是链表实现的基础，通常包含一个数据域和一个指向下一个节点的指针。