侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【递归, 迭代, 双指针】回文链表

GabrielxD
2022-10-11 / 0 评论 / 0 点赞 / 12 阅读 / 481 字 / 正在检测是否收录...

题目

234. 回文链表


给你一个单链表的头节点 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)指向头节点,递归每次比较 leftright 的节点值是否相同,并与上一次的比较结果做与运算,最后递归函数返回的就是答案。

代码

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;
    }
}
0

评论区