[Leetcode 아주 상세한 문제풀이] 19. Remove Nth Node From End of List – 코드 line 별 설명

Leetcode 문제

이번에 풀어볼 문제는 리트코드 19번 문제 Remove Nth Node From End of List 다.

우선 문제를 살펴보자.

 

리트코드 19번 문제 Remove Nth Node From End of List 링크

Remove Nth Node From End of List - LeetCode

Remove Nth Node From End of List - LeetCode

 

 

Given the head of a linked list, remove the nth node from the end of the list and return its head.

Example 1:
Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

Example 2:
Input: head = [1], n = 1
Output: []

Example 3:
Input: head = [1,2], n = 1
Output: [1]

 

 

문제 설명

문제를 간략히 살펴보자. 서로 연결된 (linked ilst)의 head가 인풋으로 주어진다. 이때 주어진 linked list에서 '끝에서 부터 n번째 노드'를 제거 후 linked list를 다시 리턴하라는 것이다. 문제 예시 1번의 경우 인풋으로 [1, 2, 3, 4, 5]가 주어졌다. 노드 1을 head로 차례대로 1->2->3->4->5 순서로 연결되어 있다. 이때 n 값이 2로 주어졌다. 따라서 뒤에서 2번째 (n=2) 노드를 제거 후 linked를 다시 출력하면 1->2->3->5된다. 따라서 [1, 2, 3, 5]를 최종적으로 리턴하면 된다. 문제를 이해하기 어렵지 않으니 곧바로 풀어보자.

 

 

문제 접근법

이 문제를 해결하기 위해 우리는 두 개의 포인터를 이용할 것이다.

문제 예시 1번을 가지고 접근해보자.

인풋으로 n=2와 [1, 2, 3, 4, 5]가 주어졌고 1->2->3->4->5로 표현된다.

이때 두 개의 포인터 (first and second)을 만들어 first (F) 포인터를 second (S) 포인터보다 n 만큼 앞에 위치시킨다.

이 경우 first 포인터는 노드 3에 second 포인터는 노드 1에 위치된다.

포인터를 위치시킨 후 두 포인터를 한 칸씩 노드 끝으로 옮긴다.

이 과정을 거치다보면 Step 3에 이르렀을 때 first 포인터가 노드 마지막에 도달하게 된다.

이때 first 포인터와 second 포인터 간 거리는 n (=2)만큼 유지된 상태다.

따라서 우리가 제거해야 하는 노드는 second 포인터가 가리키는 바로 다음 노드에 위치한다.

이제 코드로 살펴보자.

 

 

 

문제 풀이

Linked list를 표현하기 위한 class를 선언해준다. (line 1-4)

이 표현식은 파이썬에서 linked list를 표현하기 위해 자주 쓰이는 표현식이니 익숙해 지도록 하자.

이제 인풋을 입력받기 위한 함수를 정의해 준다. (line 6)

먼저 head를 가리키는 dummy node를 하나 만들어 준다. (line 8)

그리고 first, second 포인터를 이 dummy node에 위치시킨다. (line 9-10)

Dummy node를 이용하는데 몇 가지 이득이 있는데 추후에 정리해보도록 하겠다.

두 개의 포인터를 dummy node에 우선 위치시킨 후 first 포인터를 second 포인터와 n 만큼 차이나도록 이동시킨다. (line 13-14)

여기서 조금 헷갈릴 수 있는데 first 포인터를 n+1 만큼 옮겨줘야 first, second 포인터 사이에 2개의 노드가 존재한다.

그 후 first 포인터가 null이 되지 않는 동안 (linked list 끝까지) first, second 포인터를 오른쪽으로 한 칸씩 옮겨준다. (line 17-19)

위에서 설명한대로 second 포인터가 가리키는 노드 바로 다음 값이 제거해야 하는 노드다.

따라서 우리는 second 포인터의 다음값을 그 다다음값으로 연결시켜 준다. (line 22)

이 연결을 통해 second 포인터 다음값에 있던 제거해야 하는 노드를 없앤 후 linked list를 얻을 수 있다.

최종적으로 제거해야 하는 노드 제거 후 linked list를 리턴하고 종료한다. (line 24)

 

 

문제 풀이 코드

class ListNode:
    def __init__(self, value=0, next=None):
        self.value = value
        self.next = next
 
def removeNthFromEnd(head, n):
    # Create a dummy node that points to the head of the list
    dummy = ListNode(0, head)
    first = dummy
    second = dummy
 
    # Move first pointer so that the gap between first and second is n nodes apart
    for _ in range(n + 1):
        first = first.next
 
    # Move first to the end, maintaining the gap
    while first:
        first = first.next
        second = second.next
 
    # Skip the desired node
    second.next = second.next.next
 
    return dummy.next
 
# Helper function to create a linked list from a list
def create_linked_list(lst):
    head = ListNode(lst[0])
    current = head
    for value in lst[1:]:
        current.next = ListNode(value)
        current = current.next
    return head
 
# Helper function to convert linked list to list
def linked_list_to_list(head):
    lst = []
    while head:
        lst.append(head.value)
        head = head.next
    return lst
 
# Test the function with the examples
head1 = create_linked_list([1, 2, 3, 4, 5])
result1 = removeNthFromEnd(head1, 2)
print(linked_list_to_list(result1))  # Output: [1, 2, 3, 5]
 
head2 = create_linked_list([1])
result2 = removeNthFromEnd(head2, 1)
print(linked_list_to_list(result2))  # Output: []
 
head3 = create_linked_list([1, 2])
result3 = removeNthFromEnd(head3, 1)
print(linked_list_to_list(result3))  # Output: [1]
 

 

 

관련 문제

리트코드 21번 Merge two sorted lists 문제 풀이 (링크)

리트코드 23번 Merge K sorted lists 문제 풀이 (링크)

리트코드 141번 Detec cycle in a linked list 문제 풀이 (링크)

리트코드 143번 Reorder list 문제 풀이 (링크)

리트코드 206번 Reverse a linked list 문제 풀이 (링크)

 

19. Remove Nth Node From End of List