图解LeetCode——234. 回文链表网站首页 学无止境

图解LeetCode——234. 回文链表

爪哇缪斯 2024-06-17 10:29:42

简介图解LeetCode——234. 回文链表

一、题目

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

二、示例

2.1> 示例 1：

【输入】head = [1,2,2,1]
【输出】true

2.2> 示例 2：

【输入】head = [1,2]
【输出】false

提示：

链表中节点数目在范围[1, 10^5]内
0 <= Node.val <= 9

进阶：

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

三、解题思路

3.1> 思路1：转存+双指针

根据题目描述，我们需要判断链表是否是回文链表，那么比较容易想到的一种解题方式就是，我们创建一个额外的数组结构，从头节点开始遍历链表，并将其存储到数组结构中。但是对于链表结构来说，只有遍历到最后一个链表，才可以知道整个链表的长度，那么，我们就选择ArrayList来进行额外数据的存储。

在对比过程中，我们通过双指针的方式，分别从首、尾两个位置开始，依次向中心靠拢对比，当方向不同，则表示不是回文链表，否则就是回文链表了。

3.2> 思路2：倒转链表

除了上面的解题方式之外，我们也可以探究一下是否能实现 O(1) 空间复杂度解决此题。那么，由于ListNode是单向链表结构，所以只能向一个方向移动，所以为了能够改变遍历方式的话，就可以通过改变next的值来倒转链表。

那么我们就可以将整个链表的一半倒转一下，即：将A——>B倒转为A<——B；那么我们就可以从链表的“中心点”作为开始，分别向两侧进行遍历&对比。那么为题来了，怎么知道那个位置是整个链表的“中心点”呢？此处我们就可以采用快慢指针的方式，即：

【慢指针】一次移动一步，即：slow = slow.next；
【快指针】一次移动两步，即：fast = fast.next.next;

那么当快指针遍历到末尾之后，慢指针就处于了“中心点”范围内了。不过此处还有奇偶数的特殊处理：

【偶数长度链表】slow会处于中心点范围（两个节点）中的右侧节点位置；
【奇数长度链表】slow会处于中心点位置。

具体操作方式，请见下图所示：

四、代码实现

4.1> 实现1：转存+双指针

class Solution {
    public boolean isPalindrome(ListNode head) {
        List<ListNode> list = new ArrayList();
        while(head != null) {
            list.add(head);
            head = head.next;
        }
        for (int i = 0; i < list.size()/2; i++) 
            if (list.get(i).val != list.get(list.size() - i - 1).val) 
                return false;
        return true;
    }
}

4.2> 实现2：倒转链表

class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode slow = head, fast = head, pre = null;
        while(fast != null && fast.next != null) {
            ListNode temp = slow.next;
            if (pre != null) slow.next = pre;
            pre = slow;
            slow = temp;
            fast = fast.next.next;
        }
        if (fast != null) slow = slow.next; // 偶数节点
        while (slow != null) {
            if (pre.val != slow.val) return false;
            pre = pre.next;
            slow = slow.next;
        }
        return true;
    }
}