19. Remove Nth Node From End of List (Linked List, Two Pointers)

링크 - https://leetcode.com/problems/remove-nth-node-from-end-of-list/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Medium

Intuition

처음에는 맨 끝에서 n번째를 찾기위해 두번의 pass를 해야겠다고 생각이 들겠지만 이 문제는 one-pass로 풀 수 있다.

1. Dummy head를 만들고 dummy head의 next를 head로 설정한다. 그리고 node와 next_node를 dummy_head를 가리키도록 한다.

2. next_node를 n+1번 next시킨다.

3. 이제 next_node가 None이 나올때까지 next_node와 node를 next시킨다.

4. 3번이 끝나면 현재 next_node는 끝에 도달한 것이고 node는 우리가 지워야 할 node를 next에 가지고 있다. 따라서 node.next = node.next.next로 설정한다.

5. dummy_head.next를 반환한다.

Code

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy_head = ListNode(-1)
        dummy_head.next = head
        node = dummy_head
        next_node = dummy_head

        for _ in range(n+1):
            next_node = next_node.next

        while next_node is not None:
            next_node = next_node.next
            node = node.next

        node.next = node.next.next
        return dummy_head.next

Complexity

Time Complexity: O(n) 노드를 한번 pass하므로 n번의 시간이 소요된다.

Space Complexity: O(1)