当前位置：首页 > article >正文

算法—回文链表

article 2024/12/23 2:39:46

题目链接：https://leetcode.cn/problems/palindrome-linked-list/description/

题目

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

示例1：

示例1图片

输入：head = [1,2,2,1]

输出：true

示例2：

示例2图片

输入：head = [1,2]

输出：false

思路

有两种思路解决这个问题：

使用一个数据结构：栈。先进后出，遍历链表依次存到栈中，再从栈中弹出节点和链表的值比较；
反转后半段链表，双指针，一个从前往后，一个从后往前，依次比较。

其中方法一，可以扩展一下，其实只用比较前一半和后一半值就好，所以栈中只需要存放一半的的链表就好。

两个思路得出三种方法，其中用栈的方法做题的速度就比较快，不需要扣边界条件，而用反转链表双指针的方法就需要扣出边界，优点是用的额外空间少。

方法一：栈存全链表

这个方法就比较无脑了，一股脑存，再一股脑弹出：

先遍历所有节点，每个节点都压进栈
再从头节点开始，每个节点和弹出栈的值比较
有一个不一样的，就直接返回 false
所有节点遍历结束，返回 true

示意图

方法1

代码

class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        Stack<Integer> s = new Stack();
        ListNode temp = head;
        // 压栈
        while (temp != null) {
            s.push(temp.val);
            temp = temp.next;
        }
        // 弹出比较
        while (head != null) {
            if (head.val != s.pop()) {
                return false;
            }
            head = head.next;
        }
        return true;
    }
}

方法二：栈存一半链表

和第一个方法的思路一样，只是压栈的时候只压链表的后一半节点，再弹出比较。只不过需要多考虑一点边界条件。

示意图

方法2

代码

class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        // 找到中点的下一个位置
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        slow = slow.next;
        // 后半段链表压栈
        Stack<Integer> s = new Stack<>();
        while (slow != null) {
            s.push(slow.val);
            slow = slow.next;
        }
        // 链表不为 null，就弹出比较
        while (!s.isEmpty()) {
            if (head.val != s.pop()) {
                return false;
            }
            head = head.next;
        }
        return true;
    }
}

方法三：反转链表

先反转后半段链表，一个指针从前往后走，一个指针从后往前走，每次都比较一下，只要有一次不一样，就直接返回 false，全部比较完，返回 true。

示意图

方法3

代码

class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        // 反转后半段链表
        ListNode n1 = head;
        ListNode n2 = head;
        while (n2.next != null && n2.next.next != null) {
            n1 = n1.next;
            n2 = n2.next.next;
        }
        ListNode n3 = null;
        while (n1 != null) {
            n2 = n1.next;
            n1.next = n3;
            n3 = n1;
            n1 = n2;
        }
        // 判断是否回文
        n1 = head;
        while (n1 != null) {
            if (n1.val != n3.val) {
                return false;
            }
            n1 = n1.next;
            n3 = n3.next;
        }
        return true;
    }
}