給一個 Linked List,從左至右以 k 個節為一組作反轉,若不滿 k 個,則該維持原有排序。
像是在 List 中作位移的題目,多半跟 TwoPointer 的技巧是相關的。
這題也不例外,用 TwoPointer 控制兩個點互換,按題目要求解出所求。
如果由左至右,考量到後方未必有 k 個節,使用「深度優先」的遞迴函數,對於求解會比較好進行。(個人覺得比較好理解。
先檢查目前是否還有 k 個節,沒有則不逆序,有則逆序。
Python
class Solution:
def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
nextKNode = FP = head
for _ in range(k):
if not nextKNode: return head
nextKNode = nextKNode.next
lastNode = self.reverseKGroup(nextKNode, k)
for _ in range(k):
SP, FP = FP, FP.next
SP.next, lastNode = lastNode, SP
return SP