网站规划和建设的基本要求,济南传承网络技术有限公司,专科千万别学数字媒体应用技术,360免费wifi手机版目录
做题思路
代码实现
1.找到链表的中间节点
2.反转中间节点之后的链表
3.判断倒置的后半部分的链表是否等于前半部分的链表
整体代码展示
总结#xff1a; 这里是题目链接。 这道题目的意思是#xff1a;判断该链表中后半部分倒置是否跟前半部分相同#xff0c;如…
目录
做题思路
代码实现
1.找到链表的中间节点
2.反转中间节点之后的链表
3.判断倒置的后半部分的链表是否等于前半部分的链表
整体代码展示
总结 这里是题目链接。 这道题目的意思是判断该链表中后半部分倒置是否跟前半部分相同如果相同就返回true否则就返回false。
做题思路
1.先用快慢指针来找到该链表的中间节点。
2.倒置后半部分的链表。
3.判断倒置的部分是否跟前半部分相同。 代码实现
1.找到链表的中间节点
使用一个慢指针slow一次走一步一个快指针fast一次走两步。当快指针fast为null或者走到尾节点时slow所在的节点就是该链表的中间节点。
/*** 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) {if(head null) {return false; //判断head是否为空}ListNode slow head;ListNode fast head;while(fast ! null fast.next ! null) {slow slow.next;fast fast.next.next;}//此时的slow就是链表的中间节点
我们在找到了中间节点后接下来需要做的就是反转中间节点以后的链表
2.反转中间节点之后的链表 ListNode cur slow.next;
while(cur ! null) {ListNode nextNode cur.next; //nextNode用来记录cur的下一个节点cur.next slow; //将cur指向cur的前一个节点slow cur;cur nextNode;
}
//此时slow的位置就是在链表的尾节点处
3.判断倒置的后半部分的链表是否等于前半部分的链表
当链表的节点数为奇数时 当链表的节点数为偶数时 在执行这一步的时候我们需要注意当链表的节点数为偶数跟奇数的时候我们需要做出不同的判断来看前半部分的链表跟后半部分的链表是否走完了。
我们假设前半部分是从head1开始走的后半部分的链表是从head2开始走的。当链表的节点数为奇数的时候当head1跟head2相遇的时候就说明判断结束了。当链表的节点数为偶数的时候当
head1.next head2的时候我们就可以说判断结束了。
ListNode head1 head;
ListNode head2 slow;
while(head1 ! head2) {if(head1.val ! head2.val) {return false;}if(head1.next head2) {return true;}head1 head1.next;head2 head2.next;
}
return true;
整体代码展示
class Solution {public boolean isPalindrome(ListNode head) {if(head null) return false;ListNode slow head;ListNode fast head;while(fast ! null fast.next ! null) {slow slow.next;fast fast.next.next;}ListNode cur slow.next;while(cur ! null) {ListNode nextNode cur.next;cur.next slow;slow cur;cur nextNode;}while(head ! slow ){if(head.val ! slow.val) {return false;}if(head.next slow) return true;head head.next;slow slow.next;}return true;}
}
总结
所以这道题你学会了吗感谢大家的观看以后也会更新关于C语言跟Java相关的知识关注不迷路哦
