链表练习 Leetcode234.回文链表-Toy模板网

这篇具有很好参考价值的文章主要介绍了链表练习 Leetcode234.回文链表。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目传送门：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值从左到右存入数组中
在数组内进行首尾元素匹配，直至数组中间位置

第二种方法：链表法文章来源地址https://www.toymoban.com/news/detail-806094.html

首先找到链表中间节点
将中间节点后的链表翻转，得到新链表
将初始链表和新链表的元素进行匹配

数组法代码

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;
    }
};

到了这里，关于链表练习 Leetcode234.回文链表的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！