重排鏈表

題目描述：給定一個(gè)單鏈表 L 的頭節(jié)點(diǎn) head ，單鏈表 L 表示為：

L0 → L1 → … → Ln-1 → Ln 請(qǐng)將其重新排列后變?yōu)椋?/p>

L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …

不能只是單純的改變節(jié)點(diǎn)內(nèi)部的值，而是需要實(shí)際的進(jìn)行節(jié)點(diǎn)交換。

示例說(shuō)明請(qǐng)見(jiàn)LeetCode官網(wǎng)。

來(lái)源：力扣（LeetCode） ??

鏈接：https://leetcode-cn.com/problems/reorder-list/ ??

著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

解法一：鏈表遍歷

首先，如果鏈表為空或鏈表只有一個(gè)節(jié)點(diǎn)，直接返回。

否則，首先用一個(gè)棧nodes記錄所有的節(jié)點(diǎn)，并記錄鏈表節(jié)點(diǎn)的數(shù)量count；

然后，記錄插入的順序，遍歷到奇數(shù)位時(shí)，從頭結(jié)點(diǎn)方向插入鏈表；遍歷到偶數(shù)位時(shí)，從棧中取出節(jié)點(diǎn)（即從尾結(jié)點(diǎn)方向）插入鏈表。

【每日寄語(yǔ)】 人不怕有理想，不怕有夢(mèng)想。也不管它又多大，又有多遠(yuǎn)！只要你客觀的認(rèn)清自己，在道德規(guī)范之內(nèi)，堅(jiān)持自己，做你想做的，一定會(huì)有收獲的那一天！