[LeetCode] 19. Remove Nth Node From End of List

Problem

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]

Constraints:

• The number of nodes in the list is sz.
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

Follow up: Could you do this in one pass?

Solution

Approach

1. 연결 리스트의 뒤에서 n + 1번째 노드의 다음 노드를 뒤에서 n - 1번째 노드로 만들기 위해서 뒤에서 n + 1번째 노드를 가리키는 포인터가 필요하다.

2. 포인터 1을 n만큼 전진시킨다.

3. 포인터 1과 2를 포인터 1이 전진할 수 없을 때까지 동시에 전진시킨다.

4. 포인터 2가 가리키는 노드의 다음 노드를 2칸 뒤 노드를 가리키도록 하여 뒤에서 n번째 노드를 삭제한다.

Algorithm

Complexity Analysis

• Time Complexity

최악(Worst) : n의 값이 1이라면 연결 리스트의 길이(N)에 따른 for반복문(6)과 while반복문(8)의 실행횟수의 합은 N - 1이 된다. 따라서 O(N)의 시간 복잡도를 가진다.

평균(Average) : n의 값이 연결 리스트의 길이(N)의 절반인 평균의 경우라면 연결 리스트의 길이(N)에 따른 for반복문(6)과 while반복문(8)의 실행횟수의 합은 N - 1이 된다. 따라서 O(N)의 시간 복잡도를 가진다.

최선(Best) : n의 값이 연결 리스트의 길이(N)와 동일하다면 연결 리스트의 길이(N)에 관계 없이 for반복문(6)과 while반복문(8)의 실행횟수의 합은 1회가 된다. 따라서 O(1)의 시간 복잡도를 가진다.

• Space Complexity

연결 리스트의 길이(N)에 따라 감소하거나 증가하여 할당받는 공간 없이 일정한 공간을 할당받으므로 모든 경우에 O(1)의 공간 복잡도를 가진다.