Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

Example:

Given this linked list:  1->2->3->4->5

For k  = 2, you should return:  2->1->4->3->5
For k  = 3, you should return:  3->2->1->4->5

Note:

• Only constant extra memory is allowed.
• You may not alter the values in the list's nodes, only nodes itself may be changed.

Related Topics: Linked List

解題邏輯與實作

這題是 Swap Nodes in Pairs 的進階題，不同於上一題是兩兩交換，這一題是以每 k 個節點為一組翻轉鏈結串列。

不過這題在實做時，卡了我老久，主要是我試圖在一個迴圈把所整個翻轉過程，連同頭尾的指標一併搞定，所以寫起來超級的不順手。後來在這一篇中看到它的整理，這才總算讓我的思考清晰了許多：

現在有一陣列為 A->B->C->D->E ，現在我們要翻轉 BCD 三個節點，其步驟如下：
1. C->B
2. D->C
3. B->E
4. A->D

整的步驟其實分成兩個部份:
1. 先把 k 個節點翻轉，也就是步驟 1 與 2
2. 再將這 k 個節點與前後連起來，步驟 3 與 4。 

class Solution(object):
   def __init__(self,k=None):
      self.k = None
		
   def reverseKGroup(self, head, k):
      self.k = k
      if not head or self.k <= 1:
         return head

      dummy_head = ListNode(-1)
      dummy_head.next = head
      iteration = dummy_head

      while self.hasNextK(iteration):
         iteration = self.reverseNextK(iteration)

      return dummy_head.next

   def hasNextK(self, head):
      has = True
      tmp = head
      for i in range(self.k):
         if tmp.next is None :
            has = False
            break
         tmp = tmp.next

      return has

   def reverseNextK(self, head): 
      pre = head
      current = head.next
      group_end = head.next

      for i in range(self.k):
         next_node = current.next
         current.next = pre
         pre, current   = current, next_node

      head.next = pre
      group_end.next = current

      return group_end

其他連結

1. 【LeetCode】0000. 解題目錄

本文作者： 辛西亞．Cynthia
本文連結： 辛西亞的技能樹 / hackmd 版本
版權聲明： 部落格中所有文章，均採用 姓名標示-非商業性-相同方式分享 4.0 國際 (CC BY-NC-SA 4.0) 許可協議。轉載請標明作者、連結與出處！