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

말하는 감자·2024년 12월 4일

data structure leetcode linked list python two pointer 리트코드 연결 리스트 자료구조 코딩테스트 코딩테스트 준비 투 포인터 파이썬

LeetCode

목록 보기

26/32

1. 오늘의 학습 키워드

Linked List
Two Pointer

2. 문제: 19. Remove Nth Node From End of List

단계: Medium
주제: Linked List, Two Pointers
출처: https://leetcode.com/problems/remove-nth-node-from-end-of-list/description/

Description

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?

3. 문제 풀이

Step1. 문제 이해하기

이 문제는 연결 리스트의 끝에서 n번째 노드를 제거하는 문제입니다. 문제의 목표는 해당 노드를 제거한 후, 수정된 연결 리스트를 반환하는 것입니다.

Input:
- 주어지는 연결 리스트의 노드 개수는 1이상 30이하
- n은 끝에서부터 제거할 노드의 위치로 1부터 시작한다.
Output:
- 제거된 도를 제외한 새로운 연결 리스트

Example 1


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

Output:
[1, 2, 3, 5]

설명:
- 연결 리스트에서 끝에서 두 번째 노드(4)를 제거합니다.

Example 2


Input:
head = [1], n = 1

Output:
[]

설명:
- 리스트에 하나의 노드(1)만 있으므로, 이를 제거한 후 리스트는 비어 있게 됩니다.

Example 3


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

Output:
[1]

설명:
- 리스트에서 끝에서 첫 번째 노드(2)를 제거합니다.

Step2. 문제 분석하기

문제의 핵심은 끝에서 n번째 노드를 찾아 제거하는 것입니다.

연결 리스트의 길이를 파악한다면 구할 수 있습니다. 하지만 연결 리스트의 길이를 구할려면 무조건 연결 리스트를 한 번 순회한 후 다시 순회하면서 n번째를 찾아야 합니다.

더 효율적인 방법으로는 투 포인터를 사용하는 방법입니다.

두 개의 포인터를 n만큼 차이가 나도록 이동시켜, 두 포인터의 사이값을 반환하도록 하면 해결할 수 있습니다.

예를 들어, 첫번째 예시가 있습니다.

head = [1, 2, 3, 4, 5]

두 개의 포인터 s와 f가 있는데, f 포인터를 s보다 n만큼 앞에 위치시킨 다음에 계속 순회를 합니다. f포인트가 마지막까지 오게된다면 s포인트의 바로 다음 노드가 삭제할 노드에 위치하게 됩니다. 그림으로 표현하자면 다음과 같습니다.

Step3. 코드 설계

초기화:
- dummy 노드 생성: 기존 리스트 앞에 가상의 노드를 추가하여 특별한 경우(헤드 삭제)를 처리.
- fast와 slow 포인터를 dummy로 초기화.
fast를 n+1칸 이동:
- fast와 slow 사이의 거리가 n이 되도록 설정.
두 포인터 이동:
- fast를 리스트 끝까지 이동하면서 slow를 함께 이동.
- 이 과정에서 slow는 제거할 노드의 이전 노드에 위치.
노드 제거:
- slow.next = slow.next.next로 nth 노드를 건너뜀.
결과 반환:
- dummy.next를 반환.

Step4. 코드 구현

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution(object):
    def removeNthFromEnd(self, head, n):
        # https://leetcode.com/problems/remove-nth-node-from-end-of-list/submissions/1469890775
        """
        :type head: Optional[ListNode]
        :type n: int
        :rtype: Optional[ListNode]
        """

        dummy = ListNode(next=head)
        s, f = dummy, dummy
   
        for _ in range(n + 1):
            f = f.next     
        while f:
            s = s.next
            f = f.next
        s.next = s.next.next
        return dummy.next

코드 설명:
- Dummy 노드 생성:
  - 특별한 경우(예: 헤드를 제거해야 하는 경우)를 처리하기 위해 dummy 노드를 추가.
  - dummy는 기존 리스트의 앞에 가상의 노드를 삽입하여 모든 경우를 일관되게 처리.
- 두 포인터 초기화:
  - slow와 fast 포인터를 dummy로 초기화.
  - fast 포인터를 먼저 n+1 칸 이동시켜 slow와 fast 사이의 거리를 n으로 만듦.
- 포인터 이동:
  - fast 포인터가 리스트 끝에 도달할 때까지 slow와 fast를 동시에 이동.
  - 이 시점에서 slow는 제거할 노드의 이전 노드를 가리킴.
- 노드 제거:
  - slow.next를 slow.next.next로 설정하여 제거할 노드를 건너뜀.
- 결과 반환:
  - dummy.next를 반환하여 수정된 리스트를 반환.
시간 복잡도: $O(n)$
- fast 포인터가 먼저 n+1 칸 이동한 뒤, slow와 fast가 함께 리스트를 순회.
- 리스트를 한 번만 순회하므로 $O(n)$ 시간이 소요됩니다.
결과: https://leetcode.com/problems/remove-nth-node-from-end-of-list/submissions/1469890775