# iterative & recursive solutions

• O(n) time & O(1) space:
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None

class Solution(object):
"""
:type k: int
:rtype: ListNode
"""
b2 = end.next
end.next = None
pre, cur = start, start.next
while cur is not None:
pre.next = cur.next
cur.next = start
start = cur
cur = pre.next
s2.next = b2
return s2

dummy = ListNode(0)
i, start, stop = 0, dummy, dummy
while stop:
if i == k:
i = 0
start = stop = reverse(start, stop)
else:
i += 1
stop = stop.next
return dummy.next

• O(n) in time & space:

Note that this solution is taken from here.

class Solution(object):
"""
:type k: int
:rtype: ListNode
"""
while cur is not None and cnt < k:
cur = cur.next
cnt += 1
if cnt == k:
cur = self.reverseKGroup(cur, k)
while k:
k -= 1

• iterative version of solution 2, O(n) time & O(1) space:
class Solution(object):
"""
:type k: int
:rtype: ListNode
"""
def rev(start, stop, k):
while k:
tmp = start.next
start.next = stop
stop = start
start = tmp
k -= 1
return stop, start

dummy = ListNode(0)
while cur is not None:
while cur is not None and cnt < k:
cur = cur.next
cnt += 1
if cnt == k:
beg, end = rev(head, cur, cnt)