链表中的节点每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的话，我们进行反转，否则不需要进行反转。

更多题解，关注公众号《程序员学长》，让你进大厂不走弯路

github

我们下面来看一下代码实现。

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