欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode|234.回文链表

程序员文章站 2022-04-17 15:52:12
...

LeetCode|234.回文链表


题目描述

  • 等级: 简单
    请判断一个链表是否为回文链表。

示例 1:

输入: 1->2
输出: false

示例 2:

输入: 1->2->2->1
输出: true

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

思路

对于单链表回文快慢指针链表反转的考察。

“回文”是指正读反读都能读通的句子,它是古今中外都有的一种修辞方式和文字游戏,如“我为人人,人人为我”等。在数学中也有这样一类数字有这样的特征,成为回文数(palindrome number)。 [1]
设n是一任意自然数。若将n的各位数字反向排列所得自然数n1与n相等,则称n为一回文数。例如,若n=1234321,则称n为一回文数;但若n=1234567,则n不是回文数。 [1]

注意:

  1. 偶数个的数字也有回文数124421
  2. 小数没有回文数

链表反转请参考:反转单链表

通过两个快慢指针可以获取链表中的中间位置节点。(快慢指针步数相差一倍)

答案

public boolean isPalindrome(ListNode head) {
        //1、边界检查,空链表与只有一个节点的链表直接返回true
        if (head == null || head.next == null) {
            return true;
        }

        //2、通过快慢指针找到链表中间位置
        ListNode fast = head;
        ListNode slow = head;
        //当快节点走到终点,则慢节点的位置正好为链表中间
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        //fast作为后半段的起始节点
        fast = slow;
        //slow作为前半段的起始节点
        slow = head;

        //3、反转后半段链表
        //定义pre存储前一个节点
        ListNode pre = null;
        while (fast != null) {
            //指定当前要调整的点。
            ListNode temp = fast;
            //fast指针后移,走向下一个要被调整的点。
            fast = fast.next;
            //将当前的点反转
            temp.next = pre;
            //pre指针重置到最前
            pre = temp;
        }

        //4、对比前后两段链表是否相同
        //因为奇数个节点时,后半段链表比前半段链表多1个,所以循环时以前半段链表为主
        while (slow != null && pre != null) {
            if (slow.val != pre.val) {
                return false;
            }
            slow = slow.next;
            pre = pre.next;
        }
        return true;
    }

结果

LeetCode|234.回文链表


LeetCode|234.回文链表

相关标签: leetcode