# Solution with O(n) time complexity and O(1) space complexity-No recursion

• ``````class Solution:
# @param k, an integer
# @return a ListNode
previous=ListNode(0)
count=0
while cur!=None:   #count: how many elements in list
count+=1
cur=cur.next
if count<k:        #check first
numK=count/k       #numK: times of reverse
i=0
pre=previous
while i<numK:      #loop numK times
j=1
while j<k:       #each loop: reverse k nodes(like insertion)
temp=cur.next
cur.next=temp.next
temp.next=pre.next
pre.next=temp
j+=1
pre=cur
cur=cur.next
i+=1
return previous.next`enter code here`
``````

The main idea: count the number of elements in the linked list first; compare count with k, if less than k, return head; then compute numK ,times of k reverse. Then loop numK times and in each loop, reverse k nodes. The total complexity is O(n) time complexity and O(1) space complexity

• Brillant solution!

I wrote a Python version for reference.

``````class Solution:
# @param k, an integer
# @return a ListNode
length = 0
while ptr is not None:
length += 1
ptr = ptr.next
end = prev.next
first = end
for i in range(length//k):
for j in range(k-1):
insert = end.next
prev.next = insert
end.next = insert.next
insert.next = first
first = insert
prev = end
end = prev.next
first = end