LeetCode刷题（python版）——Topic25K 个一组翻转链表

一、题设

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

二、基本思路

1.当成数组来直接进行交换，再在最后存入链表中。

2.借助栈，将k个数据分批进栈出栈再链接，一边顺序遍历链表，一边存入栈中，值得注意的是循环的出口条件以及处理在最后一趟的数据不能完全存入栈中的可能性（不够k）

三、代码实现

1.way01（超时间限制）

 def reverseKGroup(self, head, k):
        def reverse(left,right,list):
            while left<right:
                temp = list[left]
                list[left] = list[right]
                list[right] = temp
        res = ListNode(999)
        start = res
        res.next = None
        list1 = []
        while head:
            list1.append(head.val)
            head = head.next
        for i in range(len(list1)):
            if (i+1) % k == 0:
                reverse(i-k,i,list1)
        for item in list1:
            node = ListNode(item)
            node.next = res.next
            res.next = node
        return start

2.栈

def reverseKGroup(self, head, k):
        # dummy为结果数组
        dummy = ListNode(-1)
        p = dummy
        while True:
            tmp = head
            # 栈用于先进后出
            vector = []
            # 每次倒计数
            count = k
            while count and tmp:
                vector.append(tmp)
                tmp = tmp.next
                count -= 1
            # 栈内无数据，链表未结束
            # 即最后一趟
            if count:
                p.next = head
                break
            while vector:
                p.next = vector.pop()
                p = p.next
            # 每倒完一次，与剩下的相连
            p.next = tmp
            head = tmp
        return dummy.next

四、效率总结

1.way01

 2.way02