25. 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.
给定一个链表的头节点，每k个节点转换前后顺序。

Example 1:

image

Input: head = [1,2,3,4,5], k = 2
Output: [2,1,4,3,5]
如果剩余的还是k的倍数，就继续反转，否则保留原样。

Example 2:

image

Input: head = [1,2,3,4,5], k = 3
Output: [3,2,1,4,5]
如果不是k的倍数，剩余的保留原序。

Constraints:

• The number of nodes in the list is n.
• 1 <= k <= n <= 5000 #k值小于节点数
• 0 <= Node.val <= 1000

思考

这题属于24. Swap Nodes in Pairs的进阶题目。将原先的两两互换，变成了每k个进行顺序互换。
这样的话难度就上来了，无法做到直截了当的判断当前节点后面是否还有k个节点。
k个节点以内的进行迭代，每k个之间进行递归。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        nodelist = []
        tmp = head
        for i in range(k):
            if bool(tmp):
                nodelist.append(tmp)
                tmp = tmp.next
            else:
                return head
            
        ret = nodelist.pop()
        ret_next = ret.next
        ret_right = ret
        
        while nodelist:
            tmp = nodelist.pop()
            ret_right.next = tmp
            ret_right = tmp
            
        if bool(ret_next):
            ret_right.next = self.reverseKGroup(ret_next, k)
        else:
            ret_right.next = None
            
        return ret

这次答案后面修改了因为如果当链表的长度正好是k的倍数的时候，需要注意将最后一个节点的next置空，不然容易出现闭环。
从结果来看这个答案虽然出来了，但是时间成本比较高。应该是O2n才对。

答案解析

class Solution:
    # 翻转一个子链表，并且返回新的头与尾
    def reverse(self, head: ListNode, tail: ListNode):
        prev = tail.next
        p = head
        while prev != tail:
            nex = p.next
            p.next = prev
            prev = p
            p = nex
        return tail, head

    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        hair = ListNode(0)
        hair.next = head
        pre = hair

        while head:
            tail = pre
            # 查看剩余部分长度是否大于等于 k
            for i in range(k):
                tail = tail.next
                if not tail:
                    return hair.next
            nex = tail.next
            head, tail = self.reverse(head, tail)
            # 把子链表重新接回原链表
            pre.next = head
            tail.next = nex
            pre = tail
            head = tail.next
        
        return hair.next

从代码来看思路和我差不多，但是运行的效率和我差了一倍。这里的时间成本是On。逻辑都一样，应该是list的append和pop比较消耗时间。
这里的反转逻辑值得捋清一下。记录头和尾节点，遍历直到尾节点为止。每次更新需要放在next位置的节点。

总结

能不用list就不用list。这个地方，我原本是可以再用一个循环来代替list的。因为list比较简单，没有链表这么复杂的逻辑结构。但是扩大了时间成本就。
题目和答案来自美国站的leetcode和中国站的力扣，仅供学习参考。