Reverse Nodes in k-Group

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

If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

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

Solution

take a look 511 Swap Two Nodes in Linked List

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

class Solution:
    # @param head, a ListNode
    # @param k, an integer
    # @return a ListNode
    def getLen(self, head):
        len = 0 
        node = head
        while node:
            len += 1
            node = node.next
        return len

    def reverseNextK(self, head, k):
        n = self.getLen(head.next)
        if n < k:
            return None
        prev = head
        p1, curr = head.next, head.next
        for i in range(k):
            tmp = curr.next
            curr.next = prev
            prev = curr
            curr = tmp

        p1.next = curr
        head.next = prev

        return p1

    def reverseKGroup(self, head, k):
        if head == None or head.next == None or self.getLen(head) < k:
            return head
        dummy = ListNode(0)
        dummy.next = head
        head = dummy
        while head and head.next:
            head = self.reverseNextK(head, k)

        return dummy.next