Reverse Nodes in k-Group(linkedlist)

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

分析

每个group里cur 和next翻转，记得只要翻k-1次，pre不要动. 翻完以后 利用pre要和前后group连接。

设置好pre的next，是为了结果返回对的header.

group内翻转，新头（cur）next指针是好的，不用担心，要设置好新尾指针（也就是pre指向的原头）的next。同时注意将pre指向新头（cur）

helper函数返回的是最后一个node(tail)，好作为将来下一个group的pre

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseKGroup(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        n = 0
        dummy = ListNode(-1)
        dummy.next = head
        cur = head
        while cur:
            n += 1
            cur = cur.next

        q = dummy
        for i in range(n // k):
            q = self.helper(q, k)#q是前group的最后一个Node

        return dummy.next

    def helper(self, pre, k):

        if not pre or not pre.next:
            return None

        cur = pre.next
        nxt = cur.next

        #prev不参与，只翻转cur 和 next
        for i in range(1, k): #1开始是因为5个元素翻转，只需要翻转4次
            nnxt = nxt.next
            nxt.next = cur
            cur = nxt
            nxt = nnxt

        #这步很重要 把本group和前面prev 后面nxt连起来，同时pre指向新头
        temp = pre.next
        pre.next.next = nxt
        pre.next = cur #pre指向新头,是为了最后的结果dummy返回头

        return temp