# 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.
#
# You may not alter the values in the nodes, only nodes itself may be changed.
#
# Only constant memory is allowed.
#
# For 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
class ListNode():
def __init__(self, x):
self.val = x
self.next = None
class Solution():
def reverseKGroup(self, x, k):
if not x:
return
cur = dummy = ListNode(0)
step, tail, tmp, point = 1, None, None, None
while x:
tmp = ListNode(x.val)
if step % k == 1:
tail, point = tmp, x
tmp.next, cur.next = cur.next, tmp
if step % k == 0:
if k == 1:
cur, point = tmp, None
else:
cur, point = tail, None
x, step = x.next, step + 1
while point:
cur.next = ListNode(point.val)
cur, point = cur.next, point.next
return dummy.next
if __name__ == "__main__":
x, x.next, x.next.next, x.next.next.next, x.next.next.next.next\
= ListNode(1), ListNode(2), ListNode(3), ListNode(4), ListNode(5)
res = Solution().reverseKGroup(x, 3)
assert '{0}->{1}->{2}->{3}->{4}'.format(res.val, res.next.val, res.next.next.val, res.next.next.next.val,
res.next.next.next.next.val) == '3->2->1->4->5'