链表中的节点每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 = nextclass 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

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