19. Remove Nth Node From End of List

뒤에서 n번째 노드를 삭제하는 문제다.

Solution

투 포인터를 사용해 해결했다.

투 포인터는 두 개의 포인터를 사용하여 배열, 연결 리스트 또는 기타 자료 구조에서 문제를 해결하는 데 사용된다. 일반적으로 배열 또는 리스트가 정렬되어 있거나 어떤 특정한 패턴을 갖고 있을 때 유용하다.

first와 second 두 개의 포인터로 연결리스트를 이동해 문제를 해결하기 때문에 투 포인터 알고리즘을 사용하는 것이다.

풀이의 핵심은 두 노드 사이에 n만큼의 갭을 만드는 것이다.

1. second를 이동시켜 n만큼의 갭을 만든다.
2. second가 끝에 도달할 때까지 두 포인터를 한 칸씩 이동시킨다. 이렇게 되면 first는 삭제해야할 노드의 바로 이전 노드에 위치하게 된다.
3. first의 연결을 삭제해야할 노드의 다음 노드와 이어주면 된다.![]

# 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]:
        first = head
        second = head
        # 두 노드 사이의 n만큼의 갭을 만듬
        for i in range(n): second = second.next
        # second가 none이면 가장 첫 번째 노드를 삭제해야함
        if not second: return head.next
        # second가 끝에 닿을 때까지 두 노드 이동
        while second.next:
            first = first.next
            second = second.next
        # 노드 삭제
        first.next = first.next.next
        return head

시간 복잡도

1. n만큼의 이동으로 O(n)
2. 두 포인터를 끝까지 이동시켜야하기 때문에 O(n)
3. 노드의 연결을 변경해주는 것은 O(1) 이므로

총 시간 복잡도는 O(n) 이다.