LinkedList : Reverse Nodes in k-Group

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

LeetCode - The World's Leading Online Programming Learning Platform

 

쉽고 깔끔하게 잘 설명하는 영상 : https://www.youtube.com/watch?v=1UOPsfP85V4

 

이 문제는 잘 모르겠어서 영상 보고 작성했다.

# 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]:
        dummy = ListNode(0, head)
        groupPrev = dummy

        while True:
            kth = self.findKth(groupPrev, k)

            if not kth:
                break
            groupNext = kth.next

            first = groupPrev.next
            prev, cur = groupNext, first
            while cur != groupNext:
                tmp = cur.next
                cur.next = prev
                prev = cur
                cur = tmp
            
            groupPrev.next = kth
            groupPrev = first

        return dummy.next

    
    def findKth(self, groupPrev, k):
        cur = groupPrev
        while cur and k:
            cur = cur.next
            k -= 1
        return cur

 

포인트가 몇 가지 있다.

1. 더미노드

2. prev, cur에서 prev를 kth노드의 다음노드로 만들기 (뒤집은 서브리스트의 마지막 노드.next 를 깔끔하게 변경함)

3. groupPrev.next = kth(뒤집은 서브리스트의 첫번째 노드)

4. groupPrev = first(뒤집기 전 첫 번째 노드 = 뒤집은 후 마지막 노드)