25. Reverse Nodes in k-Group

25. Reverse Nodes in k-Group

 

https://youtu.be/1UOPsfP85V4?si=VL2go-L_JkxKBX53

 

# 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]:
        # 더미 노드 생성: head 이전에 추가해 리스트 시작점을 쉽게 다룰 수 있도록 함
        dummy = ListNode(0, head)
        groupPrev = dummy  # 각 그룹의 이전 노드를 추적하는 포인터 (초기값은 더미 노드)

        # 반복적으로 k개의 노드를 뒤집는 작업 수행
        while True:
            # 현재 그룹에서 k번째 노드 찾기
            kth = self.getKth(groupPrev, k)

            # k번째 노드가 없으면 (남은 노드가 k보다 적다면) 루프 종료
            if not kth:  # 링크드 리스트의 마지막 그룹에 도달했는데, reverse 할만큼 크지 않으므로.
                # 더 이상 뒤집을 수 있는 그룹이 없으므로 종료
                break  # 루프 종료 

            # kth 다음 노드를 그룹의 끝 이후의 노드로 저장
            groupNext = kth.next  # 현재 그룹의 마지막 노드(kth)의 다음 노드를 저장

            # reverse group
            # 일반적으로, reverse 라면, 
            # curr = groupPrev.next 은 각 그룹의 첫번째 노드
            # prev = None 이어야 하겠지만, 
            # 여기서는 reverse 된 후, prev 가 각 그룹의 시작 노드를 가리켜야 하므로
            # prev = kth.next 로 초기화 세팅

            # 현재 그룹을 뒤집기 위한 초기화
            prev, curr = kth.next, groupPrev.next  # groupPrev.next 은 각 그룹의 첫번째 노드
            # prev: 뒤집힌 리스트의 끝부분 (그룹 이후의 노드)
            # curr: 현재 그룹에서 뒤집기를 시작할 첫 번째 노드

            # 그룹의 노드를 뒤집기 (curr가 groupNext를 만날 때까지 반복)
            # groupNext 은 그룹의 마지막, 따라서, curr가 마지막 노드까지 돌아라
            while curr != groupNext: 
                tmp = curr.next  # 현재 노드의 다음 노드를 임시 저장
                curr.next = prev  # 현재 노드의 next를 이전 노드(prev)로 변경 (역방향 연결)
                prev = curr  # prev를 현재 노드로 이동
                curr = tmp   # curr를 다음 노드로 이동

            # 그룹의 이전 노드(groupPrev)의 next를 kth로 설정
            # kth는 그룹의 마지막 노드인데, 역순으로 뒤집힌 그룹의 첫 번째 노드가 됨

            # groupPrev.next를 임시 저장 (뒤집힌 그룹의 첫 번째 노드)
            tmpGroup = groupPrev.next  # groupPrev.next는 각 그룹의 첫번째 노드

            # groupPrev.next를 kth로 설정 (뒤집힌 그룹의 첫 노드)
            groupPrev.next = kth  # kth 는 각 그룹의 마지막 노드 

            # groupPrev를 뒤집힌 그룹의 마지막 노드로 이동
            groupPrev = tmpGroup

        # 더미 노드의 next를 반환 (수정된 리스트의 새로운 head)
        return dummy.next


    # k번째 노드를 찾는 함수
    def getKth(self, curr, k):
        # curr부터 시작해 k번째 노드를 찾음
        while curr and k > 0:  # 현재 노드가 유효하고 k가 0보다 큰 동안 반복
            curr = curr.next  # 다음 노드로 이동
            k -= 1  # k를 하나씩 감소
        return curr  # k번째 노드 또는 None 반환

 

좀 정리하자면, 

 

class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        """
        groupPrev: 현재 그룹 이전 노드를 가리킴.
        kth: 현재 그룹의 마지막 노드를 가리킴., 
        		따라서, kth는 그룹내 뒤집기 이후 새로운 첫 번째 노드를 가리키게 됨
        groupNext: 현재 그룹의 마지막 노드의 다음 노드를 가리킴.
        curr와 prev: 그룹 내 노드의 순서를 뒤집는 데 사용.
        """
        # 더미 노드 생성
        dummy = ListNode(0, head)  # 더미 노드는 head 이전 노드로 설정
        groupPrev = dummy  # 각 그룹 이전 노드를 추적하는 포인터

        while True:
            # k번째 노드 찾기
            kth = self.getKth(groupPrev, k)
            if not kth:  # k번째 노드가 없다면 종료
                break
            
            # 그룹 경계 설정
            groupNext = kth.next  # 현재 그룹의 마지막 노드 다음 노드 저장
            prev, curr = groupNext, groupPrev.next  # 그룹 뒤집기를 위한 초기화
            
            # 그룹 내 뒤집기
            for _ in range(k):  # k개의 노드 뒤집기
                tmp = curr.next  # 다음 노드를 임시 저장
                curr.next = prev  # 현재 노드의 next를 이전 노드(prev)로 변경
                prev = curr  # prev를 현재 노드로 업데이트
                curr = tmp  # curr를 다음 노드로 이동
            
            # 그룹 연결
            # groupPrev: 현재 그룹 이전 노드를 가리키므로, groupPrev.next 는 현재 그룹의 첫번째 노드임
            tmp = groupPrev.next  # 현재 그룹의 첫 번째 노드 저장
            groupPrev.next = kth  # groupPrev가 현재 그룹의 마지막 노드(kth)를 가리키도록 설정
            groupPrev = tmp  # groupPrev를 다음 그룹의 첫 번째 노드로 이동
        
        return dummy.next  # 수정된 리스트 반환

    def getKth(self, node: ListNode, k: int) -> Optional[ListNode]:
        # k번째 노드를 찾는 함수
        while node and k > 0:
            node = node.next  # 다음 노드로 이동
            k -= 1  # k를 하나 감소
        return node  # k번째 노드 반환 (없으면 None 반환)

 

 

예제와 함께 살펴보기