###### tags: `Leetcode` `hard` `list` `python` `Top 100 Liked Questions`

# 25. Reverse Nodes in k-Group

## [題目來源:] https://leetcode.com/problems/reverse-nodes-in-k-group/

## 題目:
Given the head of a linked list, reverse the nodes of the list k at a time, and return the 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.

You may not alter the values in the list's nodes, only nodes themselves may be changed.


#### [圖片來源:] https://leetcode.com/problems/reverse-nodes-in-k-group/

## 解題想法:
額外寫個reverse list
主程式每次選k個node進行reverse

## Python:

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
    def insertNode(self,node):
        if not self.next:
            self.next=ListNode(node)
        else:
            self.next.insertNode(node)
    def printList(self):
        head=self
        res=[]
        while head:
            res.append(head.val)
            head=head.next
        print(res)
        
class Solution(object):
    def reverseKGroup(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        if not head:
            return None
        dummy=ListNode(0)
        dummy.next=head
        start=dummy
        while start.next:
            end=start
            #找k個進入reverse
            for i in range(k-1):
                end=end.next
                if not end.next:
                    return dummy.next
            res=self.reverse(start.next,end.next)
            new_head=res[0]
            new_tail=res[1]
            start.next=new_head
            start=new_tail
        return dummy.next
    def reverse(self,start,end):
        tail=start
        pre=end.next
        cur=None
        while pre!=end: #容易忘記!!
            cur=start.next
            start.next=pre
            pre=start
            start=cur
        return [end,tail]
    
head=ListNode(1)
head.insertNode(2)
head.insertNode(3)
head.insertNode(4)
head.insertNode(5)
head.printList()
result=Solution()
ans=result.reverseKGroup(head,2)
ans.printList()