做食品生产的网站,网站失败的原因,vue 做的网站,海口网红景点题目描述#xff1a;
给你一个单链表的头节点 head #xff0c;请你判断该链表是否为回文链表。如果是#xff0c;返回 true #xff1b;否则#xff0c;返回 false 。 因为这一题是受到876题求链表中间节点的启发#xff0c;所以在这里也加一下。
876.链表的中间结点…题目描述
给你一个单链表的头节点 head 请你判断该链表是否为回文链表。如果是返回 true 否则返回 false 。 因为这一题是受到876题求链表中间节点的启发所以在这里也加一下。
876.链表的中间结点
给你单链表的头结点 head 请你找出并返回链表的中间结点。 如果有两个中间结点则返回第二个中间结点。 思路 设置快慢指针快指针以2为步长慢指针以1为步长。因为两者是两倍关系所以当快指针遍历完成后慢指针就到达了中间节点。因为节点数分奇偶数所以循环条件以的形式。 代码
class Solution {public ListNode middleNode(ListNode head) {ListNode fasthead;ListNode slowhead;while(fast!nullfast.next!null) {fastfast.next.next;slowslow.next;}return slow;}
}然后回到234的回文链表这一题。首先按照876题的方法求得中间节点之后将中间节点后的节点的指向改为相反方向。然后从链表两侧进行遍历比较即可。改变指向的过程分为两种情况如果链表有奇数个节点那么按照一般的思想实现代码即可若链表有偶数个节点那么最中间的两个节点的判断要进行特殊处理。
代码
class Solution {public boolean isPalindrome(ListNode head) {if(headnull) {return true;}ListNode fasthead;ListNode slowhead;while(fast!nullfast.next!null) {fastfast.next.next;slowslow.next;}ListNode curslow.next;while(cur!null) {ListNode curNextcur.next;cur.nextslow;slowcur;curcurNext;}fasthead;while(fast.valslow.val) {if(slowfast) {return true;}if(fast.nextslowfast.valslow.val) {return true;}slowslow.next;fastfast.next;}return false;}
}
