关于leetcode:完虐算法链表中的节点每k个一组翻转

链表中的节点每 k 个一组翻转

问题形容

LeetCode25. K 个一组翻转链表

将给出的链表中的节点每 k 个一组翻转，返回翻转后的链表。如果链表中的节点数不是 k 的倍数，将最初剩下的节点放弃原样。你不能更改节点中的值，只能更改节点自身。

例如：

给定的链表是：1 -> 2 -> 3 -> 4 -> 5

对于 k=2，你应该返回 2 -> 1 -> 4 -> 3 -> 5

对于 k=3，你应该返回 3 -> 2 -> 1 -> 4 -> 5

剖析问题

咱们把这个问题进行拆分。

1. 咱们首先将链表依照 k 个一组进行分组。对于最初一组，有可能元素个数不满足 k 个。
2. 对于每一个分组，咱们去判断元素的个数是否为 k，如果是 k 的话，咱们进行反转，否则不须要进行反转。

咱们上面来看一下代码实现。

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    #反转链表，并且返回链表头和尾
    def reverse(self, head, tail):
        prev = tail.next
        p = head
        while prev != tail:
            next = p.next
            p.next = prev
            prev = p
            p = next
        return tail, head

    def reverseKGroup(self, head, k):
        #初始化一个哨兵节点，防止临界条件简单的判断
        prehead = ListNode(0)
        #哨兵节点指向头结点
        prehead.next = head
        pre = prehead

        while head:
            tail = pre
            #查看残余局部长度是否大于等于 k
            for i in range(k):
                tail = tail.next
                #如果残余长度小于 k, 则不须要反转，间接返回
                if not tail:
                    return prehead.next
            #tail 指向子链表的尾部
            #所以 next 指向下一个子链表的头部
            next = tail.next
            #将链表进行反转，并返回链表头和尾
            head, tail = self.reverse(head, tail)
            #把子链表从新接回原链表
            pre.next = head
            tail.next = next
            pre = tail
            head = tail.next
            
        return prehead.next

更多算法题解，请关注公众号《程序员学长》，欢送退出。