Reverse Nodes in K Groups

Problem name: isTreeSymmetric

Problem description is here.

# Definition for singly-linked list:
# class ListNode(object):
#   def __init__(self, x):
#     self.value = x
# = None
def reverseNodesInKGroups(l, k):
    head = l
    dummy = ListNode(-1) = head

    cur, cur_dummy = head, dummy
    length = 0

    while cur:
        next_cur =
        length = (length + 1) % k

        if length == 0:
            next_dummy =
            cur_dummy = next_dummy

        cur = next_cur


def reverse(begin, end):
    first =
    cur =

    while cur != end: = = = cur
        cur = 

Time Complexity

O(N + nK) # N is the length of list, n = N/K, K is group size

Solving Strategy

The key how to solve this problem is to remember previous node and next node of each K groups.

When reverse function is done, last node of the group is front, which is adjacent to just previous node of the group. First node of the group is now last, which is connected with first node of next group.