K 個(gè)一組翻轉(zhuǎn)鏈表

題目描述：給你一個(gè)鏈表，每 k 個(gè)節(jié)點(diǎn)一組進(jìn)行翻轉(zhuǎn)，請(qǐng)你返回翻轉(zhuǎn)后的鏈表。

k 是一個(gè)正整數(shù)，它的值小于或等于鏈表的長(zhǎng)度。

如果節(jié)點(diǎn)總數(shù)不是 k 的整數(shù)倍，那么請(qǐng)將最后剩余的節(jié)點(diǎn)保持原有順序。

進(jìn)階：

你可以設(shè)計(jì)一個(gè)只使用常數(shù)額外空間的算法來解決此問題嗎？ 你不能只是單純的改變節(jié)點(diǎn)內(nèi)部的值，而是需要實(shí)際進(jìn)行節(jié)點(diǎn)交換。

示例說明請(qǐng)見LeetCode官網(wǎng)。

來源：力扣（LeetCode） ??

鏈接：https://leetcode-cn.com/problems/reverse-nodes-in-k-group/ ??

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

解法一：利用棧

• 首先，如果k=1或者head為空或者head沒有后繼節(jié)點(diǎn)，直接返回空；

• 否則，遍歷head鏈表，利用一個(gè)棧kListNode，每次把k個(gè)節(jié)點(diǎn)推入棧中，然后再依次把k個(gè)節(jié)點(diǎn)從棧中取出，并且鏈表按取出的順序排列，這樣直到把鏈表遍歷完成，即完成的所有節(jié)點(diǎn)的翻轉(zhuǎn)。

注意點(diǎn)：開始記錄了一個(gè)空節(jié)點(diǎn)newHead記錄頭結(jié)點(diǎn)，這樣當(dāng)遍歷完成后直接返回newHead的下一個(gè)節(jié)點(diǎn)即為翻轉(zhuǎn)后的頭節(jié)點(diǎn)。

【每日寄語】 不是每一個(gè)貝殼里都有珍珠，但珍珠一定出現(xiàn)在貝殼中，不是每個(gè)人努力都會(huì)成功，但成功的人一定很努力。