网站宣传和推广的方法有哪些,做网站是需要多少钱,有没有转门做乐器演奏的网站,宁晋做网站1. 题目
请判断一个链表是否为回文链表。
示例 1:
输入: 1-2
输出: false示例 2:
输入: 1-2-2-1
输出: true进阶#xff1a;
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题#xff1f;来源#xff1a;力扣#xff08;LeetCode#xff09; 链接2
输出: false示例 2:
输入: 1-2-2-1
输出: true进阶
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题来源力扣LeetCode 链接https://leetcode-cn.com/problems/palindrome-linked-list 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 解题
使用快慢指针慢指针定位到中间同时上面过程中反转前半段然后从中间左边向前右边向后依次比较注意区分奇数偶数个情况
class Solution {
public:bool isPalindrome(ListNode* head) {if(!head || !head-next)return true;ListNode *fast head, *slow head, *prev NULL, *nextNode NULL;//之前没初始化prev报错了链表一定注意不要对未知的指针操作while(fast fast-next){fast fast-next-next;nextNode slow-next;slow-next prev;prev slow;slow nextNode;}if(fast ! NULL)//奇数个节点情况slow slow-next;while(slow){if(prev-val ! slow-val)return false;prev prev-next;slow slow-next;}return true;}
};
