题目
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
示例 1：
输入：head = [1,2,2,1]
输出：true
示例 2：
输入：head = [1,2]
输出：false
提示：
链表中节点数目在范围[1, 105] 内
0 <= Node.val <= 9
分析
使用快慢指针+反转链表完成
1、快慢指针的目的找到中点后进行反转，反转后将对应的后续链表进行反转
2、反转链表与head节点进行一 一比较即可
/**
* 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 {
/** 视频讲解：
https://www.bilibili.com/video/BV1VZ4y1e7aR?spm_id_from=333.337.search-card.all.click&vd_source=3f506dfd7b2a19c74f99363591d70f4c**/
// 使用快慢指针+反转链表去完成
public boolean isPalindrome(ListNode head) {
// 定义快慢指针
ListNode slow=head;
ListNode fast=head;
// 当快指针为空时找到中间节点（因为有奇数和偶数所以使用&&）
while(fast.next!=null && fast.next.next!=null){
slow=slow.next;
fast=fast.next.next;
}
// 在slow.next之后的链表进行反转
ListNode newListNode = reverseList(slow.next);
// 比较
while(newListNode!=null){
if(newListNode.val!=head.val){
return false;
}
newListNode=newListNode.next;
head=head.next;
}
return true;
}
// 定义反转函数(递归)
private static ListNode reverseList(ListNode head){
// base
if(head==null||head.next==null){
return head;
}
ListNode last=reverseList(head.next);
head.next.next=head;
head.next=null;
return last;
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/96234.html
