西宁网站建设制作公司,潍坊+网站建设,硬盘做免费嗳暧视频网站,吴川市建设工程公司网站题目传送门#xff1a;Leetcode234 给你一个单链表的头节点 head #xff0c;请你判断该链表是否为回文链表。如果是#xff0c;返回 true #xff1b;否则#xff0c;返回 false 。 示例 1#xff1a; 输入#xff1a;head [1,2,2,1]
输出#xff1a;true示例 2… 题目传送门Leetcode234 给你一个单链表的头节点 head 请你判断该链表是否为回文链表。如果是返回 true 否则返回 false 。 示例 1 输入head [1,2,2,1]
输出true示例 2 输入head [1,2]
输出false提示 链表中节点数目在范围[1, 105] 内0 Node.val 9 进阶你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题 试题解析
提供两种方法
第一种方法数组法
将链表所有节点对应的value值从左到右存入数组中在数组内进行首尾元素匹配直至数组中间位置
第二种方法链表法
首先找到链表中间节点将中间节点后的链表翻转得到新链表将初始链表和新链表的元素进行匹配
数组法代码
class Solution {//双指针方法public:bool isPalindrome(ListNode* head) {if (head-next nullptr) return true;vectorint v;//将链表中所有值复制到数组中while (head ! nullptr) {v.push_back(head-val);head head-next;}//数组前后依次比较for (int i 0, j v.size() - 1; i j; i, j--) {if (v[i] ! v[j]) {return false;}}return true;}
};
链表法代码
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:bool isPalindrome(ListNode* head) {int num 1;ListNode* pTempHead getMiddleHead(head,num);pTempHead reverseList(pTempHead);//num用来计数进行最后的匹配for(int i 0; i num; i ){if(head-val ! pTempHead-val) return false;head head-next;pTempHead pTempHead-next;}return true;}//得到中间节点ListNode* getMiddleHead(ListNode* head,int* num){ListNode* pSlow head;ListNode* pFast head;while(pFast-next ! nullptr pFast-next-next ! nullptr){(*num);pSlow pSlow-next;pFast pFast-next-next;}return pSlow;}//反转中间节点后的链表ListNode* reverseList(ListNode* head){ListNode* pNewHead nullptr;ListNode* pTake head;ListNode* pBreak head-next;while(pBreak ! nullptr){pTake-next pNewHead;pNewHead pTake;pTake pBreak;pBreak pBreak-next;}pTake-next pNewHead;return pTake;}
};
