wordpress建站教程 贴吧,网站推广的目标,网站免费正能量不下载,课程网站建设技术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;}
};
