25.md

Reverse Nodes in k-Group

Description

link

---

Solution

See Code

需要掌握和了解的是反转list的基本用法，设定开头和结尾，通过不断把第一个元素向结尾抛，注意这里的尾部需要是None，也就是list最后一个node的下一个节点，然后通过这样的循环直到反转完成即可，和#61题的旋转可以联系起来

同时要掌握通过假节点连接两个group的过程，每次都让jump指向下一个group的开头

---

Code

O(n)

# 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
        """
        dummy = jump = ListNode(0)
        dummy.next = l = r = head

        while True:
            count = 0
            while r and count < k:   # use r to locate the range
                r = r.next
                count += 1
            if count == k:  # if size k satisfied, reverse the inner linked list
                pre, cur = r, l
                for _ in range(k):
                    cur.next, cur, pre = pre, cur.next, cur  # standard reversing
                jump.next, jump, l = pre, l, r  # connect two k-groups
            else:
                return dummy.next