栈--[234]回文链表/medium

2023-12-27 19:16:13

1、题目

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

?

示例 1:

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

示例 2:

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

?

提示:

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

?

进阶:你能否用?O(n) 时间复杂度和 O(1) 空间复杂度解决此题?

Related Topics
  • 递归
  • 链表
  • 双指针

2、题目分析

回文:正读逆读的值是一样的。故第1个节点需和最后1个节点对比、第2个节点需和倒数第2个节点对比…第n个节点和倒数第n个节点对比。
因为链表无法按下标随机访问,故链表的遍历通常会借助递归实现。第1个和最后1个比,因为只遍历第1个时,无法确定最后1个。故换个角度,考虑遍历最后1个时,比对第1个
递归通常考虑3步:
1、什么时候递
2、怎么递、怎么归
3、归回来后做什么

3、解题步骤

1、递归遍历,直到最后一个节点,开始回溯。
2、从最后一个节点回溯时,也开始按头结点往下遍历。
3、回溯以后,判断当前节点和回溯的节点是否相等

4、复杂度最优解代码示例

    boolean isPalindrome = true;
    ListNode head;
    public boolean isPalindrome(ListNode head) {
        this.head = head;
        dfs(head);
        return isPalindrome;
    }

    public ListNode dfs(ListNode node) {
        if (node == null) {
            // 2、从最后一个节点回溯时,也开始按头结点往下遍历。
            return head;
        }
        
        // 1、递归遍历,直到最后一个节点,开始回溯。
        ListNode next = dfs(node.next);
        if (next.val != node.val) {
            // 3、回溯以后,判断当前节点和回溯的节点是否相等
            isPalindrome = false;
        }
        return next.next;
    }

5、抽象与扩展

对比 头和尾 时,可借助回溯法,换个角度,反过来比对尾和头

文章来源:https://blog.csdn.net/fujuacm/article/details/135191447
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。