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
# self.next = None
#
def reverseNodesInKGroups(l, k):
head = l
dummy = ListNode(-1)
dummy.next = head
cur, cur_dummy = head, dummy
length = 0
while cur:
next_cur = cur.next
length = (length + 1) % k
if length == 0:
next_dummy = cur_dummy.next
reverse(cur_dummy, cur.next)
cur_dummy = next_dummy
cur = next_cur
return dummy.next
def reverse(begin, end):
first = begin.next
cur = first.next
while cur != end:
first.next = cur.next
cur.next = begin.next
begin.next = cur
cur = first.next
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.
댓글남기기