문제 개요
단일 연결 리스트(singly linked list)와 정수 k가 주어졌을 때, 연속된 k개의 노드로 이루어진 각 그룹을 순서대로 뒤집는 것이 목표입니다.
예를 들어 리스트가 [1,2,3,4,5,6,7,8,9,10]이고 k = 3이라면, 앞의 세 노드(1, 2, 3)는 3→2→1로, 다음 세 노드(4, 5, 6)는 6→5→4로 뒤집혀 최종 결과는 [3, 2, 1, 6, 5, 4, 9, 8, 7, 10]이 됩니다. 만약 마지막에 남은 노드 수가 k보다 적다면, 해당 부분은 원래 순서를 그대로 유지합니다.
해결 알고리즘
이 문제는 더미(dummy) 노드와 여러 개의 포인터를 활용해 그룹 단위로 노드의 연결 방향을 바꾸는 방식으로 효율적으로 해결할 수 있습니다. 단계별 과정은 다음과 같습니다.
- 값이 0인 새로운 더미 노드 tmp를 생성하고, tmp의 next를 head 노드에 연결합니다.
- 포인터 prev와 curr를 초기화합니다.
- lp(이전 그룹의 마지막 노드)는 tmp로, lc(현재 그룹의 첫 노드)는 curr로 설정합니다.
- 카운터 cnt를 k로 초기화합니다.
- curr가 null이 아닌 동안 다음을 반복합니다.
- prev를 null로 초기화합니다.
- cnt가 0보다 크고 curr가 null이 아닌 동안, 현재 노드의 다음 노드를 임시 변수 following에 저장한 뒤 연결 방향을 뒤집고(prev ← curr), curr를 다음 노드로 이동시키며 cnt를 1씩 감소시킵니다.
- 그룹 하나가 완성되면 lp.next를 뒤집힌 그룹의 머리(prev)에, lc.next를 다음 그룹의 시작점(curr)에 연결합니다.
- lp와 lc를 갱신하고 cnt를 k로 재설정하여 다음 그룹 처리를 준비합니다.
- 모든 그룹의 처리가 끝나면 tmp.next를 반환합니다. 이것이 뒤집힌 리스트의 새로운 head입니다.
이 알고리즘의 시간 복잡도는 리스트를 한 번만 순회하므로 O(n)이며, 추가 공간 없이 포인터만 조작하므로 공간 복잡도는 O(1)입니다.
구현 예제
아래 코드를 통해 실제 동작을 확인해 보겠습니다.
class ListNode:
def __init__(self, data, next=None):
self.val = data
self.next = next
def make_list(elements):
head = ListNode(elements[0])
for element in elements[1:]:
ptr = head
while ptr.next:
ptr = ptr.next
ptr.next = ListNode(element)
return head
def print_list(head):
ptr = head
print('[', end="")
while ptr:
print(ptr.val, end=", ")
ptr = ptr.next
print(']')
class Solution:
def solve(self, node, k):
tmp = ListNode(0)
tmp.next = node
prev, curr = None, node
lp, lc = tmp, curr
cnt = k
while curr:
prev = None
while cnt > 0 and curr:
following = curr.next
curr.next = prev
prev, curr = curr, following
cnt -= 1
lp.next, lc.next = prev, curr
lp, lc = lc, curr
cnt = k
return tmp.next
ob = Solution()
head = make_list([1,2,3,4,5,6,7,8,9,10])
print_list(ob.solve(head, 3))
입력
[1,2,3,4,5,6,7,8,9,10], 3
출력
[3, 2, 1, 6, 5, 4, 9, 8, 7, 10]
핵심 정리
더미 노드를 사용하면 첫 번째 그룹의 head 변경을 별도의 분기 처리 없이 일관되게 다룰 수 있다는 점이 이 풀이의 핵심입니다. 또한 lp와 lc 두 포인터를 통해 뒤집힌 그룹과 다음 그룹을 자연스럽게 이어 주므로, 전체 리스트를 한 번의 순회로 처리하면서도 추가 메모리 사용 없이 문제를 해결할 수 있습니다.