[LeetCode] 25. Reverse Nodes in k-Group

25. Reverse Nodes in k-Group

Hard

Given the head of a linked list, reverse the nodes of the list k at a time, and return the 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]

 

Constraints:

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

 

Follow-up: Can you solve the problem in O(1) extra memory space?

---

문제 풀이

링크드 리스트가 하나 주어지는데, 노드들을 뒤집어야한다. 

하지만 노드의 값을 바꿀 수는 없다. 

그리고 K 값이 주어지는데, 시작 노드부터 K개수의 노드들 마다 노드들을 뒤집어 줘야한다. 

만약 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 링크드 리스트가 있다면 1과 2가 바귀고 3과 4가 바뀌고 5와 6가 바뀌고 ...

2, 1, 4, 3, 6, 5, 8, 7, 10, 9, 11로 바뀌게 된다. 

마지막으로 K값이 현재 노드에서 링크드리스트 길이를 넘으면 뒤집지 않는다.

재귀함수를 사용하여 각 K길이 만큼의 범위를 찾아야한다.

처음 노드 위치에서 K만큼 까지의 길이를 세고 만일 갯수와 K가 같다면 K길이 만큼까지 링크드 리스트를 뒤집어준다.

다시말하자면, 재귀함수 호출시 현재 노드에서(시작노드) K개 만큼 움직이고, 링크드리스트의 최종 길이를 넘지 않는다면 리스트를 역전시킨다.

소스 코드

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        def reconnect(head, k):
            new_head, p = None, head
            while k:
                next_node = p.next
                p.next = new_head
                new_head = p
                p = next_node
                k -= 1
            return new_head
        
        def bt(head, k):
            cnt = 0
            p = head

            while cnt < k and p:
                p = p.next
                cnt += 1
            if cnt == k:
                ans = reconnect(head, k)
                head.next = bt(p, k)
                return ans
            return head
        
        return bt(head, k)