深圳企业网站制作设计长沙正规竞价优化服务

力扣 234 回文链表

题目描述

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

示例 1：

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

示例 2：

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

提示：

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

思路分析

之前有写过，但那时还没有学习栈，只能通过逆置链表来进行操作，现在对栈有了一些了解后，可以更加方便的进行操作了。

这里我们利用一个数组来代替栈进行操作，非常简单，将链表的所有数据入栈，然后再遍历一次链表，每次将当前节点与栈顶元素比较，如果一一相等，说明满足回文结构。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
bool isPalindrome(struct ListNode* head) {int stack[100000]={0};int top=0;struct ListNode* cur=head;while(cur){stack[top++]=cur->val;cur=cur->next;} cur=head;while(cur){if(cur->val!=stack[top-1]){return false;}cur=cur->next;top--;}return true;
}