K个一组翻转链表

本题出处LeetCode 25题,难度为困难。

  • 问题

    给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。
    k 是一个正整数,它的值小于或等于链表的长度。
    如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。

    示例:

    给定这个链表:1->2->3->4->5
    
    当 k = 2 时,应当返回: 2->1->4->3->5
    
    当 k = 3 时,应当返回: 3->2->1->4->5
    
    说明:
    
    你的算法只能使用常数的额外空间。
    你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
    
  • 解法

    本题用递归和循环都可以解,用递归写起来比较方便。
    主要思想是将链表分为K个一组,从最后一组开始,每一组内进行翻转,返回翻转后的头部节点,将前一组的节点依次连接到后一组的头部。时间复杂度为O(N),空间复杂度为O(1)。

    class Solution:
        def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
            if k == 1:
                return head
            cur = head
            cnt = 0
            while cur and cnt != k:
                cur = cur.next
                cnt += 1
            if cnt != k:
                return head
            nxt = self.reverseKGroup(cur, k)
            while cnt > 0:
                new_head = self.move_head(head, nxt)
                nxt = head
                head = new_head
                cnt -= 1
            return nxt
    
        def move_head(self, left_head, right_head):
            """
            return: new left head
            """
            tmp = left_head.next
            left_head.next = right_head
            return tmp
    
    执行用时 :44 ms, 在所有 python3 提交中击败了99.11% 的用户
    内存消耗 :13.4 MB, 在所有 python3 提交中击败了100.00%的用户
    

发表评论

电子邮件地址不会被公开。 必填项已用*标注