Leecode 25. Reverse Nodes in k-Group

https://leetcode.com/problems/reverse-nodes-in-k-group/

The problem requires constant memory, which means that we should operate on the original list.

The natural thought is to cut the list into parts, reverse one at one time and then put them back together. Actually the reverse operation of a linked list is a vital basic skill.

Note the next_dummy and cur_dummy sentence. Before reversing, cur_dummy.next is actually the end node of this part after reversing.

Solution:

# T:O(n) S:O(1)
class Solution:
    # @param head, a ListNode
    # @param k, an integer
    # @return a ListNode
    def reverseKGroup(self, head, k):
        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
                self.reverse(cur_dummy, cur.next)
                cur_dummy = next_dummy
                
            cur = next_cur
            
        return dummy.next
    
    def reverse(self, 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

Run Time: 128 ms