[LeetCode] 203. Remove Linked List Elements

1. 오늘의 학습 키워드

• Linked List
• Recursion

---

2. 문제: 203. Remove Linked List Elements

• 단계: Easy
• 주제: Linked List, Recursion
• 출처: https://leetcode.com/problems/remove-linked-list-elements/description/?envType=problem-list-v2&envId=linked-list&difficulty=EASY

Description

Given the head of a linked list and an integer val, remove all the nodes of the linked list that has Node.val == val, and return the new head.

Example 1:

Input: head = [1,2,6,3,4,5,6], val = 6
Output: [1,2,3,4,5]

Example 2:

Input: head = [], val = 1
Output: []

Example 3:

Input: head = [7,7,7,7], val = 7
Output: []

Constraints:

• The number of nodes in the list is in the range [0, $10^4$].
• 1 <= Node.val <= 50
• 0 <= val <= 50

---

3. 문제 풀이

Step1. 문제 풀이

연결 리스트와 정수 val 이 주어졌을 때, 연결 리스트에서 노드의 값이 val 인것을 모두 제외한 연결 리스트를 반환하는 문제입니다.

연결 리스트를 순회하면서 노드 값이 val 와 같으면 제외를 하면저 진행하면 될 것으로 보입니다.

입출력을 살펴보겠습니다.

• Input:
  • 연결 리스트가 주어지며 이 연결 리스트의 길이는 0이상 $10^4$이하입니다.
  • 빈 리스트가 올 수도 있기 때문에 예외처리를 생각해야 합니다.
  • $O(n^2)$보다 효율적인 시간복잡도로 코드를 구현해야 합니다.
  • 노드와 val 의 값은 1이상 50이하입니다.
• Output:
  • val 값을 제외한 연결 리스트를 반환합니다.

Step2. 문제 분석하기

문제 정의

주어진 연결 리스트에서 특정 값 val을 가진 모든 노드를 제거하는 문제입니다. 결과로 반환되는 연결 리스트는 원래 순서를 유지해야 하며, 제거 대상이 없는 경우에는 원래 리스트 그대로 반환하면 됩니다.

입력 및 제약 조건

1. 연결 리스트의 길이:
   • 길이는 0 이상 $10^4$ 이하입니다.
   • 리스트가 비어 있을 가능성을 염두에 두고 예외 처리를 해야 합니다.
2. 노드 값 및 제거 값:
   • 노드 값과 val은 모두 1 이상 50 이하입니다.
   • 값 범위가 작기 때문에 값 자체를 활용한 간단한 조건 검사로 문제를 해결할 수 있습니다.

출력 조건

• val 값을 가진 노드들이 제거된 새로운 연결 리스트를 반환합니다.
• 제거할 값이 없거나 리스트가 비어 있으면 그대로 반환합니다.

해결 방법

1. 노드 제거 알고리즘:
   • 리스트의 각 노드를 순회하면서 노드의 값이 val과 동일한지 확인합니다.
   • 동일하다면, 해당 노드를 제거합니다. 이때, 노드 제거는 current.next를 current.next.next로 업데이트하여 수행할 수 있습니다.
2. 방법별 접근:
   • 더미 노드 활용: 리스트의 시작을 쉽게 처리하기 위해 더미 노드를 추가하여 순회합니다.
   • 더미 노드 미활용: 더미 노드 없이, head가 제거 대상인지 확인하는 로직을 별도로 처리합니다.
   • 재귀 방식: 재귀를 이용해 리스트를 끝까지 순회하며 val 값을 가진 노드를 제거합니다.

시간 복잡도

• 모든 방법에서 연결 리스트를 한 번 순회하기 때문에 시간 복잡도는 O(n)입니다.
  

그렇다면 dummy노드를 왜 활용하는지에 대한 의문이 들 수 있습니다.

왜 dummy 노드를 사용하는가?

1. 첫 번째 노드가 삭제 대상일 때 문제 발생
   • 만약 첫 번째 노드(head)의 값이 삭제 대상(val)이라면, 삭제 후 새로 시작하는 노드를 head로 설정해야 합니다.
   • 리스트의 새 시작점을 유지하려면 별도의 로직이 필요합니다.
   • 이를 피하기 위해 dummy 노드를 사용하면, 기존 리스트의 구조와 관계없이 항상 dummy.next를 반환하면 되므로 코드가 간단해집니다.
2. 코드의 일관성 유지
   • dummy를 사용하면 모든 노드를 동일한 방식으로 처리할 수 있습니다.
   • 첫 번째 노드와 이후 노드를 동일한 로직으로 삭제할 수 있습니다.

Step3. 코드 설계

방법 1: 더미 노드 활용

1. 더미 노드를 생성하여 연결 리스트의 시작점을 초기화합니다.
2. current 포인터를 통해 리스트를 순회하며 val 값과 동일한 노드를 제거합니다.
3. 더미 노드의 next를 반환합니다.

방법 2: 더미 노드 미활용

1. head 노드가 val과 같은 경우를 처리하며 리스트의 시작점을 조정합니다.
2. current 포인터를 통해 순회하며 나머지 노드들을 제거합니다.

방법 3: 재귀

1. 리스트의 끝까지 재귀적으로 탐색합니다.
2. head.next를 업데이트하면서 val 값을 가진 노드를 제거합니다.
3. 마지막에 head를 반환합니다.

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):
    # 1. Linked List using dummy
    def removeElements(self, head, val):
        # https://leetcode.com/problems/remove-linked-list-elements/submissions/1469021357
        """
        :type head: Optional[ListNode]
        :type val: int
        :rtype: Optional[ListNode]
        """
        
        dummy = ListNode()
        dummy.next = head
        curr = dummy
        
        while curr.next:
            if curr.next.val == val:
                curr.next = curr.next.next
            else:
                curr = curr.next
        return dummy.next

• 코드 설명:
  • 더미 노드를 사용하여 리스트의 시작점을 처리합니다.
  • current.next의 값을 검사하여 val에 해당하면 제거합니다.
  • 리스트 끝까지 순회하며 값을 업데이트합니다.
• 시간 복잡도: $O(n)$, 리스트를 한 번 순회합니다.
• 공간 복잡도: $O(1)$, 추가 메모리를 사용하지 않습니다.
• 결과: https://leetcode.com/problems/remove-linked-list-elements/submissions/1469021357
  

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution(object):
# 2. Linked List not using dummy
    def removeElements(self, head, val):
        # https://leetcode.com/problems/remove-linked-list-elements/submissions/1469019847
        """
        :type head: Optional[ListNode]
        :type val: int
        :rtype: Optional[ListNode]
        """
        while head and head.val == val:
            head = head.next
        
        curr = head
        while curr and curr.next:
            if curr.next.val == val:
                curr.next = curr.next.next
            else:
                curr = curr.next
        return head

• 코드 설명:
  • head가 제거 대상인지 확인하고, 제거된 새로운 시작점을 설정합니다.
  • current 포인터를 통해 리스트를 순회하며 노드를 제거합니다.
• 시간 복잡도: $O(n)$
• 공간 복잡도: $O(1)$
• 결과: https://leetcode.com/problems/remove-linked-list-elements/submissions/1469019847
  

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution(object):
# # 3. Recursion
    def removeElements(self, head, val):
        """
        :type head: Optional[ListNode]
        :type val: int
        :rtype: Optional[ListNode]
        """
        # base case
        if not head:
            return None
        
        head.next = self.removeElements(head.next, val)
        
        if head.val == val:
            return head.next
        
        return head

• 코드 설명:
  • 리스트를 재귀적으로 탐색하여 끝까지 이동합니다.
  • head.next를 재귀적으로 업데이트하며 val을 제거합니다.
  • 재귀 호출이 끝나면 head를 반환합니다.
• 시간 복잡도: $O(n)$
• 공간 복잡도: $O(n)$, 재귀 호출 스택이 추가로 사용됩니다.
• 결과: https://leetcode.com/problems/remove-linked-list-elements/submissions/1469038005

---

4. 마무리

이번 문제는 연결 리스트의 구조를 활용하여 특정 조건에 따라 노드를 제거하는 방법을 익힐 수 있는 좋은 연습이었습니다.

핵심 아이디어:

• 노드의 값을 비교하여 특정 조건을 만족할 경우 연결을 건너뛰도록 구현.
• 더미 노드를 사용하면 코드가 간결하고 명확해질 수 있습니다.
• 재귀를 활용하면 간결한 코드 작성이 가능하지만, 스택 사용에 따른 공간 복잡도가 증가할 수 있습니다.

학습 포인트:

• 연결 리스트의 노드 제거 로직에서 더미 노드의 유용성.
• 재귀를 통한 간결한 로직 작성법.
• 다양한 접근 방식의 시간 및 공간 복잡도를 고려한 선택.

테스트 코드를 실험할 수 있는 전체 코드는 다음 링크에서 확인할 수 있습니다.

읽어주셔서 감사합니다!