力扣 234 回文鏈表

題目描述

給你一個(gè)單鏈表的頭節(jié)點(diǎn)?head?，請(qǐng)你判斷該鏈表是否為回文鏈表。如果是，返回?true?；否則，返回?false?。

示例 1：

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

示例 2：

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

提示：

• 鏈表中節(jié)點(diǎn)數(shù)目在范圍[1, 105]?內(nèi)
• 0 <= Node.val <= 9

思路分析

之前有寫過(guò)，但那時(shí)還沒(méi)有學(xué)習(xí)棧，只能通過(guò)逆置鏈表來(lái)進(jìn)行操作，現(xiàn)在對(duì)棧有了一些了解后，可以更加方便的進(jìn)行操作了。

這里我們利用一個(gè)數(shù)組來(lái)代替棧進(jìn)行操作，非常簡(jiǎn)單，將鏈表的所有數(shù)據(jù)入棧，然后再遍歷一次鏈表，每次將當(dāng)前節(jié)點(diǎn)與棧頂元素比較，如果一一相等，說(shuō)明滿足回文結(jié)構(gòu)。

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