一、题目描述
给你一个单链表的头节点 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(n),空间复杂度为 O(1)。
五、总结知识点
-
链表(Linked List):
- 链表是一种常见的基础数据结构,由一系列节点组成,每个节点包含数据域和指向下一个节点的指针。
-
单链表(Singly Linked List):
-
快慢指针(Fast and Slow Pointers):
-
链表翻转(Reversing a Linked List):
- 代码展示了如何通过迭代的方式翻转链表的一部分。这是通过改变节点指针的方向来实现的。
-
递归(Recursion):
-
迭代(Iteration):
-
边界条件处理:
-
逻辑判断(Logical Comparison):
-
链表节点类定义(ListNode Class Definition):
- 虽然代码片段中没有给出
ListNode
类的定义,但它是链表实现的基础,通常包含一个数据域和一个指向下一个节点的指针。
- 虽然代码片段中没有给出
以上就是解决这个问题的详细步骤,希望能够为各位提供启发和帮助。