← 전체 회차
A-045● Day 452026.06.20hardleetcode #25neetcode150

k개 노드씩 연결 리스트 뒤집기

#linked-list#recursion
↗ leetcode #25 · reverse-nodes-in-k-group
01

문제

· problem
P.045

k개 노드씩 연결 리스트 뒤집기

↗ leetcode #25

연결 리스트의 head가 주어질 때, 리스트의 노드를 k개씩 묶어 역순으로 뒤집고 수정된 리스트를 반환하세요. k는 양의 정수이며 연결 리스트의 길이 이하입니다. 노드의 개수가 k의 배수가 아니면 끝에 남는 노드들은 그대로 유지해야 합니다. 리스트의 노드 값은 변경할 수 없으며, 노드들의 연결 관계만 변경할 수 있습니다.

제약
  • · The number of nodes in the list is n
  • · 1 ≤ k ≤ n ≤ 5000
  • · 0 ≤ Node.val ≤ 1000
// 지문은 본인 언어 요약 — 원문은 위 링크에서
입출력 예시
example 1input → output
[1,2,3,4,5]
2
[2,1,4,3,5]
example 2input → output
[1,2,3,4,5]
3
[3,2,1,4,5]
02

사전 사고

· pre-solve
● 1리스트 출력→● 2선택→● 3정답 공개
  • ☐
    끝에 k개 미만의 노드가 남으면 어떻게 하나요?
  • ☐
    노드의 값을 수정할 수 있나요?
  • ☐
    왜 더미(dummy) 노드를 사용하나요?
  • ☐
    각 반복에서 k번째 노드를 찾는 것이 필수인가요?
  • ☐
    전체 리스트를 먼저 뒤집은 후 조정하면 어떨까요?
  • ☐
    재귀로 이 문제를 풀 수 있을까요?
  • ☐
    노드 값들을 새로운 노드에 복사하여 새 리스트를 만들어야 하나요?
던질 질문에 체크하고 확인을 누르세요
// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)
03

논리 구조

· logic
● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개
// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.
step 1· 더미 노드 생성 및 초기화
○
dummy = ListNode(0, head)
○
dummy = ListNode(head)
○
dummy = head
step 2· 현재 위치에서 k번째 노드 찾기│ 중첩
○
kth = self.getKth(groupPrev, k)
○
kth = self.getKth(groupPrev.next, k)
○
kth = self.getKth(head, k)
step 3· k개 노드의 가용성 확인│ 중첩
○
if not kth:
○
if not kth.next:
○
if not groupPrev:
step 4· k개 노드의 포인터 방향 반전│ 중첩
○
prev, curr = kth.next, groupPrev.next
○
prev, curr = groupPrev.next, kth.next
○
prev, curr = None, groupPrev.next
step 5· 반전된 그룹을 리스트에 재연결│ 중첩
○
tmp = groupPrev.next
○
groupPrev.next = groupNext
○
groupPrev = kth
각 슬롯에 한 줄씩 골라보세요
// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.
04

문제풀이 · 트레이스

· solve
solution.py
1
class Solution:
2
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
3
        dummy = ListNode(0, head)
4
        groupPrev = dummy
5
6
        while True:
7
            kth = self.getKth(groupPrev, k)
8
            if not kth:
9
                break
10
            groupNext = kth.next
11
12
            # reverse group
13
            prev, curr = kth.next, groupPrev.next
14
            while curr != groupNext:
15
                tmp = curr.next
16
                curr.next = prev
17
                prev = curr
18
                curr = tmp
19
20
            tmp = groupPrev.next
21
            groupPrev.next = kth
22
            groupPrev = tmp
23
        return dummy.next
24
25
    def getKth(self, curr, k):
26
        while curr and k > 0:
27
            curr = curr.next
28
            k -= 1
29
        return curr
머릿속 dry-run 케이스
// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.
case 1
[1,2,3,4,5]
2
→
[2,1,4,3,5]
case 2
[1,2,3,4,5]
3
→
[3,2,1,4,5]
// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.