稀碎从零算法笔记Day20-LeetCode:回文链表

题型：链表、双指针

链接：206. 反转链表 - 力扣（LeetCode） 234. 回文链表 - 力扣（LeetCode）

来源：LeetCode

题目描述（红字为笔者添加）

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

回文串Ver.链表

题目样例

示例 1：

输入：head = [1,2,2,1]
输出：true

示例 2：

输入：head = [1,2]
输出：false

提示：

• 链表中节点数目在范围[1, 105] 内
• 0 <= Node.val <= 9

题目思路

回文串就是【正着/反着读一样】的串。

题目可拆分为：①反转字符串 ②判断回文串

笔者思路：将链表映射到 链表/数组。链表映射到链表：链表因为有地址的原因，映射到另一个链表即new一个新结点保存val。考虑到结构体这个蛋疼的内存以及实现难度，笔者建议直接映射到数组为优解

判断回文串这里笔者推荐双指针（两个指针双向奔赴，相遇的时候就说明是回文串）

当然，你可以直接用STL中的reverse /笑

C++代码

映射到另一个链表：（真是壮观）

/**
 * 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) {
        // 用一个新的链表来存，然后链表相同的话就是
        ListNode* temp2 = new ListNode(0);
        ListNode* temp1 = head;
        // ListNode* p;
        while (temp1 != NULL) {
            // p = temp1;
            ListNode *temp = new ListNode(0);
            temp->val = temp1->val;
            temp1 = temp1->next;
            temp->next = temp2->next;
            temp2->next = temp;
        }
        ListNode* real = temp2->next;
        temp1 = head;
        while (temp1 != NULL && real != NULL) {
            //cout << temp1->val << " " << real->val;
            if (temp1->val != real->val)
                return 0;
            
            temp1 = temp1->next;
            real = real->next;
            
        }
        delete temp2;
        return 1;
    }
};

用了reverse（懒狗！）

/**
 * 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) {
        // 数值映射到数组
        // 字符串判断回文串
        vector<int> num;
        while(head != NULL)
        {
            num.push_back(head->val);
            head = head->next;
        }
        vector<int> temp = num;
        reverse(num.begin(),num.end());
        for(int i=0;i<num.size();i++)
        {
            if(num[i] != temp[i])
                return 0;
        }
        //string str = to_string(num);
        return 1;

    }
};

双指针

/**
 * 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) {
        //链表映射到数组 
          vector<int> num;
        while(head != NULL)
        {
            num.push_back(head->val);
            head = head->next;
        }
        int left=0,right=num.size()-1;
        while(left < right)
        {
            if(num[left] != num[right])
                return 0;
            left++;
            right--;
        }
        return 1;
    }
};

结算页面

时空复杂度都很高。。