当前位置：首页 > news >正文

链表练习 Leetcode234.回文链表

news 来源：原创 2024/5/8 9:58:42

题目传送门：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;vector<int> 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;}
};