25. Reverse Nodes in k-Group（Hard）

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

Example:

Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

Note:

• Only constant extra memory is allowed.
• You may not alter the values in the list's nodes, only nodes itself may be changed.

Solution1:

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

class Solution:
    def reverseKGroup(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        if k==1:
            return head
        Head = ListNode(0) #辅助头结点
        Head.next = head
        begin = Head
        end = Head
        while begin and end:
            count = 0
            while count<k and end: #end前进k步
                end = end.next
                count += 1
            if not end: #判断是否足够k个节点
                break
            begin.next = self.reverse(begin.next,k) #begin的next开始，反转k个结点，然后记录下新的后继
            #在反转之后更新下次的begin和end
            end = begin
            for _ in range(k):
                end = end.next
            begin = end
        return Head.next

    def reverse(self,head,k): #反转以head为头结点的k的节点，返回反转后的头结点
        Head = ListNode(0)
        Head.next = head
        work = Head
        Next = None
        for count in range(k,0,-1):  #每次选倒数第count个节点
            find = head
            for _ in range(count-1):
                find = find.next
            if count == k: #保存这一次的后续，防止断链
                Next = find.next
            work.next = find
            work = work.next
        find = Head
        for _ in range(k):
            find = find.next
        find.next = Next  #接上链子
        return Head.next

Solution2: 用栈来做，用递归代码会简短很多

class Solution:
    def reverseKGroup(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        ans = []
        temp = head
        for _ in range(k):
            if head is not None:
                ans.append(head)
            else:
                return temp
            head = head.next
        first = ans.pop()
        res = first
        for _ in range(k-1):
            first.next = ans.pop()
            first = first.next
        first.next = self.reverseKGroup(head,k)
        return res