牛客網(wǎng)高頻算法題系列-BM13-判斷一個(gè)鏈表是否為回文結(jié)構(gòu)

題目描述

給定一個(gè)鏈表，請(qǐng)判斷該鏈表是否為回文結(jié)構(gòu)。 回文是指該字符串正序逆序完全一致。

原題目見：BM13 判斷一個(gè)鏈表是否為回文結(jié)構(gòu)

解法一：鏈表遍歷

首先，考慮特殊情況，如果鏈表為空或只有一個(gè)鏈表，默認(rèn)是回文結(jié)構(gòu)，直接返回true。

否則，使用一個(gè)額外的list進(jìn)行處理，處理過程如下：

• 遍歷原鏈表，將鏈表中所有結(jié)點(diǎn)的值添加到一個(gè)list中；

• 遍歷list中的值判斷該鏈表是否是回文結(jié)構(gòu)，遍歷過程如下：

• 遍歷list中0-list.size()/2的值；

• 判斷i的值和list.size() - i - 1的值是否相等，如果不相等，則不可能是回文結(jié)構(gòu)，直接返回false。

• 遍歷完成后，如果list中首尾的相應(yīng)位置的值都相等，說明原鏈表是回文結(jié)構(gòu)，返回true。

代碼

1.01^{365} ≈ 37.7834343329 ??

0.99^{365} ≈ 0.02551796445 ??

相信堅(jiān)持的力量！