linked list - 특정 값을 갖는 노드 제거하기 (1)재귀적 방법

from typing import List

class ListNode:
    def __init__(self, val):
        self.val = val  # 노드는 값을 갖는 부분과
        self.next = None  # 다음 자료를 가리키는 부분으로 이루어진다.

def createList(in_list: List[int]) -> ListNode:  # List[int]를 ListNode 로 리턴하는 함수.
    if len(in_list) == 0:
        raise RuntimeError("in_list must have data")
    head_node = ListNode(in_list[0])
    last_node = head_node
    for idx in range(1, len(in_list)):
        node = ListNode(in_list[idx])
        last_node.next = node
        last_node = node
    return head_node

def printNodes(node: ListNode):
    crnt_node = node
    while crnt_node is not None:
        print(crnt_node.val, end=' ')
        crnt_node = crnt_node.next
    print()


# 연결 리스트에서 특정 값을 갖는 노드를 삭제하는 함수 구현하기
class ElementRemover:
    def __init__(self, val):
        self.__val = val

    # (1) 재귀적 방법
    def recursive(self, node: ListNode) -> ListNode:
        #####(case C)
        if not node:  # 삭제하려는 노드가 인자로 유효하게 주어지지 않았다면
            return None  # None 을 리턴한다.
        next_node = self.recursive(node.next)  # 다시 현재 노드의 다음 노드를 recursive 로.
        #####(case A)
        if node.val == self.__val:  # 현재 노드의 값이 삭제하고자 하는 값과 같다면
            return next_node  # (자신은 사라지고) 뒤에서 넘어온(올) next_node 값을 그대로 리턴해준다. 
        #####(case B)
        else:  # 현재 노드의 값이 삭제하는 값이 아니라면
            node.next = next_node  # 자신의 Next 로서 뒤에 아이가 재귀함수를 거치면서 리턴된 값을 취한다.
            return node  # 현재 노드를 리턴해줌.

        ## 즉, 1 > 3 > 5 > 7 > 3 > 1 이런 연결리스트이고, 삭제할 값이 3이라면
        ## 포인터가 1에 있을 때 "리턴값은 자기자신 : 1"  ## case B
        ## 1에서 next_node는 3이 recursive 돌았을 때 리턴값인데
        ## 그 값은 case A 에 해당하므로 (삭제해야 하는 값이므로)
        ## 반환해야 하는 값은 next_node 이다. 그런데 이를 위해 재귀함수에 5를 넣은 리턴값을 구해야 한다.
        ## 5에 넣은 리턴값은? case B에 해당하므로 현재 노드를 반환한다. 즉 "리턴은 5"
        ## 그러면서 이 노드의 다음 노드값은 next_node여야 하므로 7이 recursive를 돌았을 때의 리턴값이다.
        ## 7의 경우 case B에 해당하므로 현재 노드인 7을 리턴
        ## 이 노드의 다음은 next_node 이고, 이는 7 뒤의 3이 recursive를 돌았을 때의 리턴 값.
        ## 3이 재귀함수를 돈다면 case A 에 해당. 즉 그 다음 수인 1을 재귀함수에 넣은 리턴값을 리턴해야 한다.
        ## 1이 재귀함수를 돈다면 case B에 해당. 현재 노드인 1을 리턴.
        ## 아 이 노드의 다음은 이 노드 다음인 (none..)을 재귀함수에 넣었을 때의 리턴값으로 할당되는데
        ## node가 아니니까 case C. 리턴 값은 None이고 node연결은 이제 더이상 없는 것.?!


head = createList([1, 3, 5, 7, 3, 1])
printNodes(head)

remover = ElementRemover(3)
ret = remover.recursive(head)
printNodes(ret)

https://www.youtube.com/watch?v=UDzObr6WxYE&list=PLDV-cCQnUlIbV0z51Mwbbe-tdW2JDS-bR&index=4