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

一、题目描述

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

示例 1：

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

示例 2：

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

提示：

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

二、解题思路

1. 快慢指针法找到链表中点：我们可以使用两个指针，快指针每次移动两步，慢指针每次移动一步。当快指针到达链表末尾时，慢指针恰好到达链表中点。

2. 翻转后半部分链表：当找到链表中点后，我们可以将后半部分链表翻转，以便与前半部分链表进行比较。

3. 比较前后两部分链表：将前半部分链表与翻转后的后半部分链表进行比较，如果每个节点的值都相等，则为回文链表。

4. 恢复链表（可选）：如果题目要求不改变原链表结构，我们需要在比较完成后，将后半部分链表再次翻转回来。

三、具体代码

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 类的定义，但它是链表实现的基础，通常包含一个数据域和一个指向下一个节点的指针。

以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。

原文地址：https://blog.csdn.net/weixin_62860386/article/details/142407486

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！