[Leetcode]203. Remove Linked List Elements

1. 문제 :

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, 104].
1 <= Node.val <= 50
0 <= val <= 50

 

2. 풀이 : 

첫 번째, 이 코드는 반복문을 통해 val과 current_node.val이 같다면 그 node를 삭제시키고 before_node와 삭제될 값의 다음 node를 연결시키는 방식의 코드이다. 직관적이고 좋다고 생각해서, 이 코드를 작성했다. 그리고 , loop가 끝난 뒤, 코드 초기에 temp에 head값을 저장했다, head pointer를 다시 바꿔준다. 

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

 

두 번째, recursion을 이용한 풀이다. recursion을 이용한 풀이는 작성해 보았지만, 너무 길게 적었었다. recursion을 쓰는 이유는 code를 간결하게 하기 위함 아닌가? 하지만, 그렇지 못했다. 

다음번에 적용해야할 recursion 공식 : 

1. 제일 적은 케이스 즉 , base case에서 만족하는지 조사 

2. 문제를 visualize하기 

3. 각각의 case들끼리의 상관관계 보기 

4. pattern을 만들기 

5. base code 와 recursive code의 조합 만들기  

 

++ n = 1 일 때, 만족한다, n = k-1일 때, 만족한다면 , n = k일 때도 만족한다. 

n = k-1일때, 만족한다고 가정하고 ,  n = k일 때 과감 없이 쓰자. 

 

def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
            def recursive_check(head):
                nonlocal before 
                if head is None:
                    return 
                if head.val == val:
                    head = head.next 
                    before.next = head 
                else:
                    before = head 
                    head = head.next 
                return recursive_check(head) 
            before = ListNode() 
            before.next = head 
            temp = before
            recursive_check(head) 
            head = temp.next 
            return head

위 코드 같은 경우는 완벽한 recursive라고 보기는 힘들다. 그 이유는 간결하지 않기 때문이다. 마치 loop문에서 while 값만 뺀 느낌이랄까. 이 코드의 문제점은 뭘까? 내가 직접 head값을 움직여놓고 재귀함수를 부른다는 것이다. 이 부분을 고쳐야 한다. 

 

class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        # 기본적인 기저 사례: head가 None이면 반환
        if head is None:
            return None
        
        # 재귀적으로 다음 노드를 처리
        head.next = self.removeElements(head.next, val)
        
        # 현재 노드의 값이 val와 같으면 다음 노드를 반환 (현재 노드 삭제)
        if head.val == val:
            return head.next
        
        # 그렇지 않으면 현재 노드를 그대로 반환
        return head

이렇게 고쳐야한다. 간결하고, 나는 기존에 있던 head만 신경 쓰고, head.next는 다음 함수에 넘겨버린다. 그리고 신경을 끈다. 이게 핵심이다.