25. K 个一组翻转链表 [hard]

https://leetcode-cn.com/problems/reverse-nodes-in-k-group/

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

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

示例：

给你这个链表：1->2->3->4->5

当 k = 2 时，应当返回: 2->1->4->3->5

当 k = 3 时，应当返回: 3->2->1->4->5

说明：

你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

通过次数79,578 | 提交次数128,961

First Try

2020-07-06

其实就是倒排任意大小的链表，但是一段时间没写，竟然写错了两个版本的倒排，wtf.

本来可以使用0024题的解法，使用额外的空间存储来简化，但这样空间复杂度就是O(K)了，不被允许，因此只能在原地倒排链表。

对于链表倒排，在head前面加多个dummy节点，真的是方便了许多。在计数上，后续处理上，都减少了例外情况。另外倒排关键是有head和tail两个节点，找到了tail节点就方便一路怼了，但很容易写错成只有tail第一，后面的全跟之前一样的顺序。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reverseKGroup(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        # 相当于在k的子集内进行链表倒序
        # 第一个k次达到时候，需要特殊处理，因为没有head，其他元素都有
        # 问题是只允许O(1)的额外空间，也就是不允许O(k)的额外列表了。。

        # def filp(head, tail):
        #     start, end = tail, head
        #     while head != start:
        #         tail.next = head
        #         tail = tail.next
        #         head = head.next
        #     return start, end

        # def flip(head, tail):
        #     start, end = tail ,head 
        #     while head != start:
        #         print(head, start)
        #         prehead = head
        #         head = head.next
        #         prehead.next = head.next
        #         head.next = prehead
        #     return start, end               

        def flip(head, tail):
            """倒序，需要每次都在原来的末尾后面插入head"""
            start, end = tail, head 
            while head != tail:
                downstream = tail.next 
                tail.next = head 
                head = head.next
                tail.next.next = downstream
            return start, end 
                 

        dummy = ListNode(None)
        dummy.next = head
        head = node = dummy 

        c = 0
        while node:
            nextnode = node.next  # 不提前把下一级搞出来又容易出bug
            if c > 0 and c % k == 0:
                a, b = flip(head.next, node)
                head.next = a
                head = b
                head.next = nextnode
                        
            c += 1
            # nextnode需要在前面提前运行才行，不然node都被颠倒了，node.next不对了              
            # node = node.next
            node = nextnode 

        return dummy.next

执行用时：40 ms, 在所有 Python 提交中击败了56.86%的用户
内存消耗：14.3 MB, 在所有 Python 提交中击败了8.33%的用户

25. K 个一组翻转链表 [hard]​

First Try​

25. K 个一组翻转链表 [hard]

First Try