题目描述
给你一个单链表的头节点 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)
空间复杂度解决此题?
解题方案
- C 双指针
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
bool isPalindrome(struct ListNode* head) {
int num[100000] = {0}; // 用来存放数据
int n = 0; // 计算列表长度
while(head != NULL) // 遍历链表
{
num[n++] = head->val; // 将数据更新到数组中
head = head->next;
}
for(int i = 0, j = n - 1; i < j; i++, j--)
{
if(num[i] != num[j]) // 不满足回文
{
return false;
}
}
return true;
}
复杂度分析
时间复杂度:O(n),其中 n 指的是链表的元素个数
空间复杂度:O(n),其中 n 指的是链表的元素个数
- 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 *p = head;
stack<int> val_stack; // 创建一个栈
while(p != NULL)
{
val_stack.push(p->val); // 将链表数据依次入栈
p = p->next;
}
p = head; // 从头遍历链表
while(p != NULL)
{
if(p->val != val_stack.top()) // 对比链表数据和栈顶元素
{
return false;
}
val_stack.pop(); // 移除栈顶元素
p = p->next;
}
return true;
}
};