[Leetcode] 25. Reverse Nodes in k-Group_해설, 풀이, 설명

---

안녕하세요, HELLO

 

오늘은 Leetcode 알고리즘 문제 '25. Reverse Nodes in k-Group'에 대해서 살펴보고자 합니다. 

 

알고리즘 문제, 코드, 해설 그리고 Leetcode에서 제공해 준 solution 순서대로 정리하였습니다.

---

STEP 1. 'Reverse Nodes in k-Group' 알고리즘 문제

 

STEP 2. 'Reverse Nodes in k-Group' 코드(code)

 

STEP 3. 'Reverse Nodes in k-Group' 해설

 

STEP 4. 'Reverse Nodes in k-Group' solution

 

반응형

 

STEP 1. 'Reverse Nodes in k-Group' 알고리즘 문제

 

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.

 

linked list의 head가 주어졌을 때, 리스트의 노드 k를 한 번에 반전시키고 수정된 리스트를 반환합니다.

k는 양의 정수이며 linked list의 길이보다 작거나 같아야 합니다. 노드 수가 k의 배수가 아닌 경우 결국 제외된 노드는 그대로 유지되어야 합니다.

리스트의 노드에 있는 값은 변경할 수 없으며 노드 자체만 변경할 수 있습니다.

 

Constraints:

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

---

STEP 2. 'Reverse Nodes in k-Group' 코드(code)

 

■ Runtime: 73 ms, Beats 10.79%
■ Beats: 18.4 MB, Beats 6.48%

 

# 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]:
        tmp_lst = []
        while head:
            tmp_lst.append(head.val)
            head = head.next

        # If K is less than n
        if len(tmp_lst) < k :
            return head

        # If K is more than n
        loop_seq = len(tmp_lst)//k
        
        empty_lst = []
        for seq in range(loop_seq):
            point = k-1
            while point >= 0:
                empty_lst.append(tmp_lst[seq*k + point])
                point -= 1

        check_num = (seq +1) * k
        while check_num < len(tmp_lst):
            empty_lst.append(tmp_lst[check_num])
            check_num += 1

        final_head = None
        for val in empty_lst[::-1]:
            final_head = ListNode(val, final_head)
        return final_head

---

STEP 3. 'Reverse Nodes in k-Group' 해설

 

문제는 head 값을 k 길이 내에서 역순으로 정렬해야 됩니다. 그리고 나머지 값은 원본과 동일한 순서로 저장됩니다.

즉, k = 2, head = [1,2,3,4,5]는 2 범위인 [1, 2] 그리고 [3, 4]를 내부에서 역순으로 정렬하여 [2, 1] 그리고 [4, 3]으로 변경합니다. 그리고 나머지 [5]를 연결하여, 최종적으로 [2,1,4,3,5]로 반환해야 합니다.

 

이를 위해서, head 길이와 linked list를 리스트로 변환해서 저장했습니다. 그리고 head 길이를 k로 나눈 몫의 범위만큼 역순으로 새로운 리스트에 저장하고, 나머지 값을 append 했습니다.

 

그리고 이를 최종적으로 linked list로 변환해서 반환했습니다.

1. while head # 리스트 변환 과정
2. range(loop_seq) + while check_num < len(tmp_lst) # 역순 정렬 + 나머지 값 append
3. for val in empty_lst[::-1] # linked list 변환

상기 과정에서 총 3n만큼 time complexity가 발생하고, O(3n)로 문제를 해결했습니다.

 

728x90

 

STEP 4. 'Reverse Nodes in k-Group' solution

 

방법은 유사하지만, edge case를 사전에 해결한 방식입니다.

1. k가 1인 경우, head 변화가 없기에 그대로 반환
2. head를 k로 나눈 몫에 대해서, 반복문 진행
3. 이때, reversed group을 반복문을 진행하면서 업데이트 수행

위 과정을 통해, 속도와 데이터 점유율에서 좋은 결과를 이뤘습니다.

 

■ Runtime: 62 ms Beats 48.9%
■ Beats: 17.5 MB Beats 54.75%

 

class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        # Base case
        if k==1:
            return  head
        # find lenght of linked list
        lenght = 0
        curr = head
        while curr:
            curr = curr.next
            lenght+=1
            
        groups = lenght//k # no. of groups, we want to reverse
        ans = ListNode(-1) #dummy node : next of this node point head of requried linked list
        last = ans # pointer last : point the last node of each reversed group of  k

        while groups:
            count = 1 #count the size of reversed group
            st = head # start node of group which will be last node after reverse the group 
            pre , curr , nxt = None, head , head.next #reverse the group by taking three pointers
            while count<k:
                curr.next = pre
                pre , curr , nxt = curr , nxt  , nxt.next # move each pointer to next node
                count+=1
                
            curr.next = pre
            # curr point the start node of reversed group 
            last.next = curr # asign last node->next of previous reversed group to start node of this reversed group 
            last = st # asign last pointer to end node of currently reveresed group       
            head = nxt
            last.next = head # take care if last group have size less than k
            groups -=1 # reduce the count of unreversed groups
            
        return ans.next # return head of required linked list

---

■ 마무리

 

오늘은 Leetcode 알고리즘 문제 '25. Reverse Nodes in k-Group'에 대해서 알아봤습니다.

좋아요와 댓글 부탁드리며,

오늘 하루도 즐거운 날 되시길 기도하겠습니다 :)

감사합니다.