25. Reverse Nodes in k-Group

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 list's nodes, only nodes themselves may be changed.

 

Example 1:

Input: head = [1,2,3,4,5], k = 2 Output: [2,1,4,3,5]

Example 2:

Input: head = [1,2,3,4,5], k = 3 Output: [3,2,1,4,5]

Example 3:

Input: head = [1,2,3,4,5], k = 1 Output: [1,2,3,4,5]

Example 4:

Input: head = [1], k = 1 Output: [1]

 

Constraints:

• The number of nodes in the list is in the range sz.
• 1 <= sz <= 5000
• 0 <= Node.val <= 1000
• 1 <= k <= sz

class Solution(object):
    def reverseKGroup(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        if k == 1:
            return head
        
        l = []
        cur = head
        while cur:
            l.append(cur.val)
            cur = cur.next
            
        for i in range(0, len(l), k):
            if len(l) < (i+k):
                break
            l[i:i+k] = l[i:i+k][::-1]

        head = ListNode(l[0])
        cur = head
        for el in l[1:]:
            tmp = ListNode(el)    
            cur.next = tmp
            cur = cur.next
            
        return head

Runtime: 44 ms, faster than 44.35% of Python online submissions for Reverse Nodes in k-Group.

- 이 솔루션보다 stack을 이용하여 풀었으면 runtime이 더 개선되겠다..