---
title: 【LeetCode】0025. Reverse Nodes in k-Group
date: 2019-01-07
is_modified: false
disqus: cynthiahackmd
categories:
- "面試刷題"
tags:
- "LeetCode"
---

{%hackmd @CynthiaChuang/Github-Page-Theme %}
<br>

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.

<!--more-->
**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

<br>

>**Note:**
>- Only constant extra memory is allowed.
>- You may not alter the values in the list's nodes, only nodes itself may be changed.

<br>

**Related Topics:** `Linked List`

## 解題邏輯與實作
這題是 [Swap Nodes in Pairs](/a2XDdf9RTg2KAIalSdsd1A) 的進階題，不同於上一題是兩兩交換，這一題是以每 k 個節點為一組翻轉鏈結串列。

不過這題在實做時，卡了我老久，主要是我試圖在一個迴圈把所整個翻轉過程，連同頭尾的指標一併搞定，所以寫起來超級的不順手。後來在[這一篇](https://shenjie1993.gitbooks.io/leetcode-python/025%20Reverse%20Nodes%20in%20k-Group.html)中看到它的整理，這才總算讓我的思考清晰了許多：

現在有一陣列為 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. 解題目錄](/x62skqpKStKMxRepJ6iqQQ)

<br><br>

> **本文作者**： 辛西亞．Cynthia
> **本文連結**： [辛西亞的技能樹](https://cynthiachuang.github.io/LeetCode-0025-Reverse-Nodes-in-k-Group) / [hackmd 版本](https://hackmd.io/@CynthiaChuang/LeetCode-0025-Reverse-Nodes-in-k-Group)
> **版權聲明**： 部落格中所有文章，均採用 [姓名標示-非商業性-相同方式分享 4.0 國際](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.en) (CC BY-NC-SA 4.0) 許可協議。轉載請標明作者、連結與出處！