服装设计类网站,赣州建设培训网官网,免费的室内装修设计软件,中国小康建设网 是个什么网站1. 题目
编写一个函数#xff0c;检查输入的链表是否是回文的。
示例 1#xff1a;
输入#xff1a; 1-2
输出#xff1a; false 示例 2#xff1a;
输入#xff1a; 1-2-2-1
输出#xff1a; true 进阶#xff1a;
你能否用 O(n) 时间复杂度和 O(1)…1. 题目
编写一个函数检查输入的链表是否是回文的。
示例 1
输入 1-2
输出 false 示例 2
输入 1-2-2-1
输出 true 进阶
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题来源力扣LeetCode 链接https://leetcode-cn.com/problems/palindrome-linked-list-lcci 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 解题
先快慢指针找到中点断开注意快指针要先走一步偶数节点的时候保证均分反转后半段跟前半段比较即可
class Solution {
public:bool isPalindrome(ListNode* head) {if(!head || !head-next)return true;ListNode *halfhead NULL, *fast head-next, *slow head;while(fast fast-next){fast fast-next-next;slow slow-next;}halfhead slow-next;slow-next NULL;//断开halfhead reverseList(halfhead);//反转后半段while(head halfhead)//比较{if(head-val ! halfhead-val)return false;head head-next;halfhead halfhead-next;}return true;}ListNode* reverseList(ListNode *head){ListNode *prev NULL, *cur head, *nt cur-next;while(cur cur-next){cur-next prev;prev cur;cur nt;nt nt-next;}cur-next prev;return cur;}
};
