题目
给你一个单链表的头节点 head
,请你判断该链表是否为回文链表。如果是,返回 true
;否则,返回 false
。
示例 1:
输入:head = [1,2,2,1]
输出:true
示例 2:
输入:head = [1,2]
输出:false
提示:
- 链表中节点数目在范围
[1, 10^5]
内 0 <= Node.val <= 9
**进阶:**你能否用 O(n)
时间复杂度和 O(1)
空间复杂度解决此题?
解题
方法一:递归 后序遍历
思路
首先递推到链表的尾节点(right
),然后维护一个指针(left
)指向头节点,递归每次比较 left
与 right
的节点值是否相同,并与上一次的比较结果做与运算,最后递归函数返回的就是答案。
代码
class Solution {
ListNode left;
public boolean isPalindrome(ListNode head) {
left = head;
return recursive(head);
}
boolean recursive(ListNode right) {
if (right == null) return true;
boolean res = recursive(right.next);
res &= left.val == right.val;
left = left.next;
return res;
}
}
方法二:快慢指针找中点 递归反转 迭代判等
思路
先使用快慢指针的方法找到链表中点,注意如果链表节点有奇数个还要把中点向后推一位,因为要保证后半部分的节点数小于前半部分。
然后再利用递归反转后半部分链表。
最后比较前后部分链表的每一个节点是否都相同来判断该链表是否回文。
代码
class Solution {
public boolean isPalindrome(ListNode head) {
ListNode mid = getMid(head);
ListNode left = head, right = reverse(mid);
while (right != null) {
if (left.val != right.val) return false;
left = left.next;
right = right.next;
}
return true;
}
ListNode getMid(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return fast == null ? slow : slow.next;
}
ListNode reverse(ListNode head) {
ListNode curr = head, newNext = null, newPrev;
while (curr != null) {
newPrev = curr.next;
curr.next = newNext;
newNext = curr;
curr = newPrev;
}
return newNext;
}
}
评论区