链表练习 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值从左到右存入数组中
• 在数组内进行首尾元素匹配，直至数组中间位置

第二种方法：链表法

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

数组法代码

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