汽车美容网站模板,帮别人做网站的单子,旅行社网站系统,网站怎么做免费推广题目
给你一个单链表的头节点 head #xff0c;请你判断该链表是否为回文链表。如果是#xff0c;返回 true #xff1b;否则#xff0c;返回 false 。
示例 输入#xff1a;head [1,2,2,1]
输出#xff1a;true思路
找到链表的中间节点#xff1a;可以使用快慢指针…题目
给你一个单链表的头节点 head 请你判断该链表是否为回文链表。如果是返回 true 否则返回 false 。
示例 输入head [1,2,2,1]
输出true思路
找到链表的中间节点可以使用快慢指针法快指针每次前进两步慢指针每次前进一步当快指针到达链表末尾时慢指针刚好处于链表的中间位置。反转后半部分链表从中间节点开始将链表的后半部分进行反转操作。比较前后两部分链表从链表的头部和中间节点开始依次比较前后两部分链表的节点值是否相等。如果所有节点的值都相等则链表为回文链表否则不是回文链表。
Code
class Solution {
public:bool isPalindrome(ListNode* head) {if (head nullptr || head-next nullptr) {return true; // 空链表或只有一个节点的链表为回文链表}ListNode* middle findMiddle(head);ListNode* secondHalf reverseList(middle-next);ListNode* p1 head;ListNode* p2 secondHalf;bool result true;while (p2 ! nullptr) {if (p1-val ! p2-val) {result false;break;}p1 p1-next;p2 p2-next;}middle-next reverseList(secondHalf); // 恢复链表的原始顺序return result;}private:ListNode* findMiddle(ListNode* head) {ListNode* slow head;ListNode* fast head;while (fast-next ! nullptr fast-next-next ! nullptr) {slow slow-next;fast fast-next-next;}return slow;}ListNode* reverseList(ListNode* head) {ListNode* prev nullptr;ListNode* curr head;while (curr ! nullptr) {ListNode* nextNode curr-next;curr-next prev;prev curr;curr nextNode;}return prev;}
};
