【LeetCode】0025 K个一组翻转链表

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

# -*- coding:utf-8 -*-

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None
class Solution:
    def reverseKGroup(self, head: ListNode, k: int):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        cur = head
        count = 0
        while cur and count != k:
            cur = cur.next
            count += 1
        if count == k:
            cur = self.reverseKGroup(cur, k)
            while count:
                tmp = head.next
                head.next = cur
                cur = head
                head = tmp
                count -= 1
            head = cur
        return head
if __name__ == '__main__':
    n1 = ListNode(1)
    n2 = ListNode(2)
    n3 = ListNode(3)
    n4 = ListNode(4)
    n5 = ListNode(5)
    n1.next = n2
    n2.next = n3
    n3.next = n4
    n4.next = n5
    print(Solution().reverseKGroup(n1, 5))

思路：这道题刚开始我的思路是交换，也就是说交换0和k-1个链表，然后是1和k-2一直到中间位置，然后向下递归，后来发现这个方法实现起来有一定难度，因为这个链表是单向链表，无法向前找k-2节点，而每次都遍历查找的代价有有点高，因此采用移动而不是交换的方法来进行交换。简单说就是每次都将不在交换序列中的链表（也就是不是前k个以及已经交换过的节点）扔到头结点的后面，这样头节点就后移了，也就进行交换了。（简单图示如下，瞎画凑合看emm）

思考：还有一个比较好的思路就是用栈，免去了链表连来连去的问题。

栈的特性，先进后出刚好满足交换原则，1234进栈出栈则为4321，因此将链表依次入栈，出栈之后依次链起来即可。