网站百度搜不到了,网线水晶头的接线方法,百度网站推广找谁做,企业工商信息查询app问题背景
给你一个单链表的头节点 h e a d head head#xff0c;请你判断该链表是否为 回文链表#xff08;回文 序列是向前和向后读都相同的序列#xff09;。如果是#xff0c;返回 t r u e true true#xff1b;否则#xff0c;返回 f a l s e false false。
数据…问题背景
给你一个单链表的头节点 h e a d head head请你判断该链表是否为 回文链表回文 序列是向前和向后读都相同的序列。如果是返回 t r u e true true否则返回 f a l s e false false。
数据约束
链表中节点数目在范围 [ 1 , 1 0 5 ] [1, 10 ^ 5] [1,105] 内 0 ≤ N o d e . v a l ≤ 9 0 \le Node.val \le 9 0≤Node.val≤9
解题过程
非常经典的套路先用快慢指针求出链表的中间节点再从中间节点开始反转链表最后从头开始和反转后的链表比对是否相等即可。
虽然题目没有要求判断的题最好不要修改输入所以最后再把链表反转回来。
具体实现
/*** 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 middle middle(head);// 从中间节点开始反转middle reverse(middle);ListNode check1 head, check2 middle; // 存一下两个指针防止丢失while(check2 ! null) {if(check1.val ! check2.val) {return false;}check1 check1.next;check2 check2.next;}// 把链表反转回来middle reverse(middle);return true;}private ListNode middle(ListNode head) {ListNode slow head, fast head;// 模板化的判断非空慢指针走一步同时快指针走两步最后慢指针会停在链表中点处while(fast ! null fast.next ! null) {slow slow.next;fast fast.next.next;}return slow;}private ListNode reverse(ListNode head) {// 初始化三个指针分别指向头节点和它的前后节点// 由于循环中会率先更新 next 指针这个变量可以不初始化ListNode pre null, cur head, next;while(cur ! null) {// 反转操作next cur.next;cur.next pre;// 轮转指针pre cur;cur next;}return pre; // 注意要返回 pre}
}
