leetcode刷题笔记-234. 回文链表（java实现）
题目描述
请判断一个链表是否为回文链表。
示例 1:
输入: 1->2
输出: false
示例 2:
输入: 1->2->2->1
输出: true来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/palindrome-linked-list
解题思路
寻找回文串的核心思想是从中心向两端扩展。
因为回文串可能是基数也可能是偶数，长度为奇数时只存在一个中心点，长度为偶数时存在两个中心点。
判断是否为回文串的思路比较简单，不需要考虑奇偶情况，从两端向中心逼近即可。
（因为回文串是对称的，所以正着读和倒着读应该是一样的，这一特点是解决回文串问题的关键）
判断单链表是否为回文链表：
关键单链表无法倒着遍历，无法使用双指针技巧。最简单的办法是把链表反转存入新的链表，比较两者是否一致。
其实，借助二叉树后序遍历的思路，不需要显示反转链表也可以倒叙遍历链表。
链表其实也是可以有前序和后序遍历的
实际上就是把链表节点放入一个栈，然后再拿出来，这时候元素的顺序是反的。
还有更好的思路：
先通过双指针的快慢指针找到链表的中点；
ListNode slow, fast;
slow = fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// slow 指针现在指向链表中点
如果fast没指向null说明链表长度为奇数（slow还要再往前一步），否则为偶数；
if (fast != null)
slow = slow.next;
从slow开始反转后边的链表就可以开始比较回文了。
该方法总体时间复杂度为O（n），空间复杂度为O（1）
解题代码
方法一：
//链表后序遍历方法，通过递归方式反转链表
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode l;
public boolean isPalindrome(ListNode head) {
l = head;
return compVal(head);
}
private boolean compVal(ListNode r) {
if(r == null) {
return true;
}
boolean result = compVal(r.next);
if(result && (r.val == l.val)) {
l = l.next;
return true;
}
return false;
}
}
方法二：更好的思路
//通过快慢指针方式
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
//快慢指针找到链表中点
ListNode s = head, f = head;
while(f != null && f.next != null) {
s = s.next;
f = f.next.next;
}
if(f != null) {
s = s.next;
}
//反转后半段链表
ListNode p=head, q=reverse(s);
//比较两段链表
while(q!=null) {
if(p.val != q.val) {
return false;
}
p = p.next;
q = q.next;
}
return true;
}
public ListNode reverse(ListNode h) {
ListNode p = null, c = h;
while(c != null) {
ListNode n = c.next;
c.next = p;
p = c;
c = n;
}
return p;
}
}
赞 (0)