LeetCode 203(Remove Linked List Elements, Python)

1. 문제 링크

• https://leetcode.com/problems/remove-linked-list-elements/

Remove Linked List Elements - LeetCode

 

2. 문제 설명

• 연결 리스트 head와 val이라는 정수가 주어졌을 때, 연결 리스트에서 Node.val == val인 모든 노드를 제거하여 new head를 반환 
• 예시1) head = [1,2,6,3,4,5,6], val = 6 이면, [1,2,3,4,5]를 반환
• 예시2) head = [7,7,7,7], val = 7 이면 []를 반환

3. 처음 풀이

• 일반적으로 연결리스트를 풀던 방식으로 접근하였음 
  • head가 None이면 None을 return하고,
  • cur이라는 복사본을 만든 뒤에
    • while문을 돌리면서, 만약 cur.next.val이 val과 동일하면, cur.next 를 cur.next.next로 미뤄주고,
    • 동일하지 않으면, cur를 cur.next 가 되게 이동시켰음.
  • 이 때 발생한 한 가지 문제가 [7,7,7,7] 과 같은 경우, next만 살펴봐서 첫번째 Node의 값인 7이 없어지지 않고, [7]이 반환되었고
    • while문이 끝나고, head.val이 val인지 체크해서, 그렇다면 head = head.next 하는 로직을 하나 추가해주었음

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:

        if head is not None and head.val == val:
            head = head.next 
        
        if head is None:
            return None

        cur = head

        while cur.next is not None:
            if cur.next.val == val: 
                cur.next = cur.next.next 
            else:
                cur = cur.next
        
        if head.val == val:
            head = head.next 

        return head

 

4. 다른 풀이

• 재귀로 접근해서 깔끔하게 풀이한 코드들도 있었음. (나중에 살펴보니 related topic에 'reccursion'이 적혀있었음. 출제자의 의도)
• 재귀가 종료되는 조건으로
  • head 가 None일 때 None을 반환하고 
• 만약 head.val이 val과 같다면, head.next를 재귀시킨 값을 반환하고, 그렇지 않으면 head를 반환하는 구조로 작성

class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        if not head:
            return None
        
        head.next = self.removeElements(head.next, val)
        return head.next if head.val == val else head

 

5. 배운 점

• 아직도 재귀가 직관적으로 해석되지 않지만, 좀 더 익숙해지다보면, 좀 더 간결한 코드로 짤 수 있을 것 같다.
• 처음 접근한 풀이는 약간의 rule들이 좀 더 추가되어 아쉬웠고, 다른 풀이는 로직이 좀 더 깔끔하다.