문제 개요
연결 리스트(Linked List)가 하나 주어졌다고 가정해 보겠습니다. 우리가 해야 할 일은 리스트의 끝에서 N번째에 위치한 노드를 제거한 후, 수정된 리스트의 헤드(head)를 반환하는 것입니다.
예를 들어, 리스트가 [1, 2, 3, 4, 5, 6]이고 n = 3이라면, 끝에서 세 번째 노드인 '4'가 제거되어 결과적으로 [1, 2, 3, 5, 6]이 반환됩니다.
해결 접근 방식
이 문제는 두 포인터(Two Pointers) 기법을 활용하면 리스트를 한 번만 순회하면서 효율적으로 해결할 수 있습니다. 앞서 나가는 포인터(front)와 뒤따르는 포인터(back) 사이의 간격을 n + 1로 유지하면, front가 리스트의 끝에 도달했을 때 back은 자연스럽게 제거할 노드 바로 앞에 위치하게 됩니다.
구체적인 알고리즘 단계는 다음과 같습니다.
- 노드가 하나뿐인 경우 처리: 헤드 다음에 노드가 없다면, 제거 후 리스트가 비게 되므로 None을 반환합니다.
- 포인터 초기화: front와 back을 모두 head로 설정하고, counter는 0, flag는 False로 초기화합니다.
- 간격 확보: counter가 n 이하일 동안 front를 앞으로 이동시킵니다. 이 과정에서 front가 리스트 끝을 넘어간다면(flag = True), 제거 대상이 헤드 노드임을 의미합니다.
- 동시 이동: front가 리스트 끝에 도달할 때까지 front와 back을 함께 이동시킵니다.
- 노드 제거: flag가 False라면 back.next를 back.next.next로 변경하여 대상 노드를 건너뛰고, 제거된 노드의 next를 None으로 정리합니다.
- 헤드 제거 처리: flag가 True라면 제거할 노드가 헤드이므로, head를 head.next로 변경합니다.
- 결과 반환: 수정된 head를 반환합니다.
파이썬 구현 예제
아래 코드를 통해 실제 구현 방법을 더 자세히 살펴보겠습니다.
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(object):
def removeNthFromEnd(self, head, n):
if not head.next:
return None
front = head
back = head
counter = 0
flag = False
while counter <= n:
if(not front):
flag = True
break
front = front.next
counter += 1
while front:
front = front.next
back = back.next
if not flag:
temp = back.next
back.next = temp.next
temp.next = None
else:
head = head.next
return head
head = make_list([1,2,3,4,5,6])
ob1 = Solution()
print_list(ob1.removeNthFromEnd(head, 3))
입력
[1,2,3,4,5,6]
3
출력
[1,2,3,5,6]
복잡도 분석
이 알고리즘은 리스트를 한 번만 순회하므로 시간 복잡도는 O(L)(L은 리스트의 길이)입니다. 또한 포인터 몇 개만 추가로 사용하므로 공간 복잡도는 O(1)로, 메모리 측면에서도 매우 효율적입니다.