문제 개요
연결 리스트 L과 정수 k가 주어졌을 때, 앞에서 k번째 노드와 뒤에서 k번째 노드의 값을 서로 교환한 후 최종 리스트를 반환하는 프로그램을 만들어 보겠습니다.
예를 들어 입력이 L = [1,5,6,7,1,6,3,9,12], k = 3이라면 출력은 [1,5,3,7,1,6,6,9,12]가 됩니다. 앞에서 3번째 노드는 6이고 뒤에서 3번째 노드는 3이므로, 이 두 값이 서로 맞바뀌게 됩니다.
해결 접근 방법
이 문제는 투 포인터(two pointer) 기법을 활용하면 리스트를 한 번만 순회하면서도 효율적으로 해결할 수 있습니다. 단계별 과정은 다음과 같습니다.
- temp를 L(헤드)로 초기화합니다.
- i를 0부터 k-2까지 반복하며 temp를 다음 노드로 이동시켜, 앞에서 k번째 노드에 도달하게 합니다.
- firstNode를 temp로 지정합니다.
- secondNode를 L(헤드)로 지정합니다.
- temp의 다음 노드가 null이 아닌 동안 secondNode와 temp를 함께 한 칸씩 앞으로 이동시킵니다.
- firstNode의 값과 secondNode의 값을 서로 교환합니다.
- L을 반환합니다.
여기서 핵심은 두 포인터 사이의 간격을 유지하는 것입니다. temp가 먼저 k-1칸 앞선 상태에서 두 포인터를 동시에 이동시키면, temp가 마지막 노드에 도달하는 순간 secondNode는 정확히 뒤에서 k번째 노드에 위치하게 됩니다. 이 방식의 시간 복잡도는 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(']')
def solve(L, k):
temp = L
for i in range(k-1):
temp = temp.next
firstNode = temp
secondNode = L
while temp.next:
secondNode = secondNode.next
temp = temp.next
firstNode.val , secondNode.val = secondNode.val , firstNode.val
return L
L = [1,5,6,7,1,6,3,9,12]
k = 3
print_list(solve(make_list(L), k))입력
[1,5,6,7,1,6,3,9,12], 3
출력
[1, 5, 3, 7, 1, 6, 6, 9, 12]