个人网站 不备案,wordpress媒体文件夹,网站的结构怎么做,盐田区网站建设题目#xff1a;给你一个单链表的头节点 head #xff0c;请你判断该链表是否为回文链表。如果是#xff0c;返回 true #xff1b;否则#xff0c;返回 false 。
示例 1#xff1a; 输入#xff1a;head [1,2,2,1]
输出#xff1a;true示例 2#xff1a; 输入…题目给你一个单链表的头节点 head 请你判断该链表是否为回文链表。如果是返回 true 否则返回 false 。
示例 1 输入head [1,2,2,1]
输出true示例 2 输入head [1,2]
输出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) {/**思路1.判断链表是否为空或者单节点链表为空直接返回true2.添加快慢指针快指针一次走2步慢指针一次走1步即快指针的速度是慢指针的2倍此时当快指针遍历到链表的最后慢指针遍历到链表的中间3.反转后半部分链表与前半部分链表逐一匹配一一对应返回true否则返回false*/if (head null || head.next null){return true;}// 声明快慢指针ListNode fastNode head;ListNode slowNode head;// 遍历链表慢指针找到链表中点while(fastNode ! null fastNode.next ! null){slowNode slowNode.next;fastNode fastNode.next.next;}//反转慢指针后半部分链表与前半部分链表逐一匹配ListNode resversHalfList resversList(slowNode);ListNode P1 head;ListNode p2 resversHalfList;boolean res true;while(p2 ! null){if(P1.val ! p2.val){res false;break;}P1 P1.next;p2 p2.next;}// resversList(resversHalfList);return res;}private ListNode resversList(ListNode head){ListNode pre null;ListNode cur head;while(cur ! null){ListNode nextTemp cur.next;cur.next pre;pre cur;cur nextTemp;}return pre;}}
总结错误思路写这道题时我最初的思路是找到中间最大的数然后依次向左右两边逐一遍历判断是否对称相等一一对应为true否则为false。没错上面的思路有很大的问题且时间空间复杂度会相对复杂因此我使用AI查询了我解题思路的错误所在。一在回文链表当中最大的数可能不止一个此时的回文链表在找到最大的中间数依次向左右两侧依次遍历也可能会得到与预期相反的结果二通过指针向左右依次遍历判断不如快慢指针上述代码有相应的解释如何找到链表的中点找到中点后将前后链表部分反转首先可判断前后部分的长度是否相等不相等直接返回false长度相等时则继续逐一匹配直到确定是回文链表时返回true使用快慢指针来遍历链表的时间和空间复杂度相对而言较简单耗时较短。
