19. Remove Nth Node From End of List

주어진 연결 리스트에서 뒤에서부터 n 번째 노드를 제거하는 것입니다. 아래는 문제의 자세한 설명입니다:

문제 설명:
주어진 연결 리스트에서 뒤에서부터 n 번째 노드를 제거하고, 수정된 연결 리스트의 헤드를 반환하는 함수를 구현하세요.

 

Input: 1->2->3->4->5, n = 2
Output: 1->2->3->5

설명:
위 예시에서, 주어진 연결 리스트는 1->2->3->4->5입니다. 이 리스트에서 뒤에서부터 2번째 노드를 제거하면 결과로 1->2->3->5가 나와야 합니다.

노트:

n은 항상 유효한 값으로 주어집니다.
연결 리스트를 한 번만 순회하여 문제를 해결하세요.
이 문제는 뒤에서부터 n 번째 노드를 찾는데 빠른 포인터와 느린 포인터 기법을 사용하면 효과적으로 해결할 수 있습니다. 주어진 연결 리스트를 한 번만 순회하면서 원하는 노드를 찾고, 그 노드를 삭제한 후 수정된 연결 리스트의 헤드를 반환하면 됩니다.

 

ListNode* removeNthFromEnd(ListNode* head, int n) {
       if (head == nullptr) return head;

        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* fast = dummy;
        ListNode* slow = dummy;

        // Advance the fast pointer by n + 1 steps.
        for (int i = 0; i < n + 1; i++) {
            fast = fast->next;
        }

        // Move the fast and slow pointers together until the fast pointer reaches the end.
        while (fast != nullptr) {
            fast = fast->next;
            slow = slow->next;
        }

        // Remove the nth node from the end.
        slow->next = slow->next->next;

        return dummy->next;
    }

 

뒤에서부터 n 번째 노드를 찾고 앞에서부터 n 번째 노드를 찾는 것은 동일한 목표를 달성하는 방법 중 하나입니다. 코드에서 앞에서부터 n 번째 노드를 찾는 것은 실제로 뒤에서부터 n 번째 노드를 제거하는 방법으로도 작동합니다.


뒤에서부터 n 번째 노드를 찾기 위해서는 리스트의 전체 길이를 알아야 하고, 그런 다음 길이에서 n을 뺀 위치에 있는 노드를 제거합니다.

앞에서부터 n 번째 노드를 찾기 위해서는 다음과 같이 작동합니다:

fast 포인터를 n 노드만큼 앞으로 이동시킵니다.
그런 다음 fast 포인터와 slow 포인터를 함께 이동시켜 fast 포인터가 끝에 도달하면 slow 포인터는 정확히 n 번째 노드를 가리킵니다.
이후 slow 포인터를 사용하여 n 번째 노드를 제거합니다.
두 번째 방법은 뒤에서부터 n 번째 노드를 찾는 것과 동일한 결과를 제공합니다. 즉, 코드에서 앞에서부터 n 번째 노드를 찾는 방법은 문제의 요구 사항을 충족시키는 방법 중 하나입니다. 이것이 코드에서 사용된 방법이며, 뒤에서부터 n 번째 노드를 제거하는데 사용됩니다.