signed

QiShunwang

“诚信为本、客户至上”

【LeetCode-⭐Hot100】234. 回文链表

2021/4/26 23:43:07   来源:

题目链表:https://leetcode-cn.com/problems/palindrome-linked-list/

难度:简单

题目描述

请判断一个链表是否为回文链表。

测试用例

示例 1:

输入: 1->2
输出: false

示例 2:

输入: 1->2->2->1
输出: true

题解

第一次遍历链表,把遍历的结果存入栈中。然后进行第二次遍历链表,依次和栈中元素对比。

时间复杂度:O\left ( n \right )

空间复杂度:O\left ( n \right )

代码

// 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) {
        stack<int> s;
        ListNode *p = head;
        while (p){
            s.push(p->val);
            p = p->next;
        }
        p = head;
        while (p){
            if (p->val != s.top())
                return false;
            p = p->next;
            s.pop();
        }
        return true;
    }
};