题目链接:https://leetcode.cn/problems/palindrome-linked-list/description/
题目
给你一个单链表的头节点 head
,请你判断该链表是否为回文链表。如果是,返回 true
;否则,返回 false
。
示例1:
输入:head = [1,2,2,1]
输出:true
示例2:
输入:head = [1,2]
输出:false
思路
有两种思路解决这个问题:
其中方法一,可以扩展一下,其实只用比较前一半和后一半值就好,所以栈中只需要存放一半的的链表就好。
两个思路得出三种方法,其中用栈的方法做题的速度就比较快,不需要扣边界条件,而用反转链表双指针的方法就需要扣出边界,优点是用的额外空间少。
方法一:栈存全链表
这个方法就比较无脑了,一股脑存,再一股脑弹出:
- 先遍历所有节点,每个节点都压进栈
- 再从头节点开始,每个节点和弹出栈的值比较
- 有一个不一样的,就直接返回
false
- 所有节点遍历结束,返回
true
示意图
代码
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;}
}
方法二:栈存一半链表
和第一个方法的思路一样,只是压栈的时候只压链表的后一半节点,再弹出比较。只不过需要多考虑一点边界条件。
示意图
代码
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
。
示意图
代码
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;}
}
总结
这是一道 LeetCode 简单题,适合新手锻炼寻找链表相关的边界条件,思路不难,代码实现起来也比较容易。
Tips:你能用第三种方法使用完之后将链表恢复吗?快来试试吧!