給你一個(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)保持原有順序焊傅。
示例 :
給定這個(gè)鏈表：1->2->3->4->5
當(dāng) k = 2 時(shí)，應(yīng)當(dāng)返回: 2->1->4->3->5
當(dāng) k = 3 時(shí)鸦列，應(yīng)當(dāng)返回: 3->2->1->4->5
說(shuō)明 :
你的算法只能使用常數(shù)的額外空間租冠。
你不能只是單純的改變節(jié)點(diǎn)內(nèi)部的值，而是需要實(shí)際的進(jìn)行節(jié)點(diǎn)交換薯嗤。
思路
- 已經(jīng)翻轉(zhuǎn)的部分和剩下的鏈表連接起來(lái)
（1）用pre 來(lái)表示需要翻轉(zhuǎn)部分鏈表的前驅(qū)；
（2）每次翻轉(zhuǎn)前纤泵，首先確定翻轉(zhuǎn)的范圍骆姐，需要進(jìn)行k次循環(huán)镜粤，
start (= pre.next) 和 end(k循環(huán)得到) 來(lái)確定翻轉(zhuǎn)區(qū)間；
（3）對(duì)需要翻轉(zhuǎn)的鏈表進(jìn)行翻轉(zhuǎn)玻褪，pre.next = 翻轉(zhuǎn)好的鏈表肉渴；
（4）更新pre，end.
def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
if not head or not head.next:
return head
new_head = ListNode(0)
new_head.next = head
pre, end = new_head, new_head
while end.next:
i = 0
while i < k and end != None:
end = end.next
i += 1
if end == None:
break
start = pre.next
nxt = end.next
end.next = None
pre.next = self.reverse(start)
start.next = nxt
pre = start
end = pre
return new_head.next
def reverse(self, head):
pre = None
cur = head
while cur:
nxt = cur.next
cur.next = pre
pre = cur
cur = nxt
return pre
- 使用棧存儲(chǔ)需要翻轉(zhuǎn)的節(jié)點(diǎn)
（1）對(duì)要翻轉(zhuǎn)的部分進(jìn)行k次循環(huán)带射，同時(shí)要保證這部分長(zhǎng)度是大于k的同规；
（2）如果剩下的鏈表數(shù)不夠k，則跳出循環(huán)窟社，將已經(jīng)翻轉(zhuǎn)好的部分和剩下的鏈表相連券勺；
（3）如果夠k，則對(duì)棧內(nèi)的元素進(jìn)行出棧灿里，將已經(jīng)翻轉(zhuǎn)好的部分和這些出棧的節(jié)點(diǎn)依次相連关炼；
（4）更新前驅(qū)節(jié)點(diǎn)和頭結(jié)點(diǎn)。
def reverseKGroup2(self, head: ListNode, k: int) -> ListNode:
if not head or not head.next:
return head
new_head = ListNode(0)
pre = new_head
while True:
count = k
stack = []
tmp = head
while count and tmp:
stack.append(tmp)
tmp = tmp.next
count -= 1
if count:
pre.next = head
break
while stack:
pre.next = stack.pop()
pre = pre.next
pre.next = tmp
head = tmp
return new_head.next
