[Leetcode 25] - Reverse Nodes in k-Group w/ Python

 

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.

 

 

연결 리스트와 k가 주어졌을때 리스트가 끝날때까지 k 만큼의 노드를 뒤집어야 된다.

k는 항상 정수이고 리스트의 길이 보다 같거나 작다

노드의 값을 바꿀수 없고 노드를 향하는 방향만 바꿀수 있다

 

 

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

 

 

---

 

 

 

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]

 

 

 

 

---

 

 

문제를 접근할때 너무 복잡해서 재귀를 써야겠다고 생각했다.

이를 통해 k번 만큼 뒤집은 다음, head를 수정해서 노드 방향만 바꾸는 방식을 만들었다.

 

class Solution:
    def reverseKGroup(self, head: 'ListNode', k: int) -> 'ListNode':
        count = 0
        curr = head
        prev = None
        
        # k 만큼 방향을 뒤집기
        while count < k and curr: 
            temp = curr.next
            curr.next = prev
            prev = curr
            curr = temp
            count += 1

		# k번 만큼 노드가 남아있지 않다면 마지막 재귀에 도달한걸 확인
        # 이를 통해 남은것만 바꾸고 리턴
        if count < k:
            curr = prev
            prev = None
            while curr:
                temp = curr.next
                curr.next = prev
                prev = curr
                curr = temp
            return head

        head.next = self.reverseKGroup(curr, k) # 다음 헤드 노드에 저장
        return prev # 제일 앞에 있는 값을 리턴

 

 

확실히 리스트를 통해서 재귀를 구현하는데 시간이 조금 오래 걸린다는걸 알게 되었다.

계속해서 같은 작업을 해야된다면 빠르게 작업을 나누는 함수 또는 재귀를 통해

문제를 정복해 나가는걸 익숙해 해야될 것 같다.

 

 

좋은 결과!~