링크드 리스트(여러 element삭제하기)

리스트의 노드를 삭제하는 방법은 previous 노드를 삭제 노드의 next 노드와 연결해주면 된다.

 

하지만, 이 경우 head의 노드를 삭제하는 것이 불가능하다.

이를 해결하기 위해 recursive 방법을 쓸 수 있다.

 

def recursive(self, node: ListNode) -> ListNode:
        if not node:
            return None
        
        next_node = self.recursive(node.next)

        if node.val == self.__val:
            return next_node
        else:
            node.next = next_node
            return node

 

iterative 방법으로도 구현가능하다. head node 앞에 dummy node를 만들어서 사용하면 문제가 된 edge case를 처리할 수 있다.

 

from typing import List

class ListNode:
  def __init__(self, x):
    self.val = x
    self.next = None

def createList(in_list: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) -> None:
        self.__val = val

    def recursive(self, node: ListNode) -> ListNode:
        if not node:
            return None
        next_node = self.recursive(node.next)
        if node.val == self.__val:
            return next_node
        else:
            node.next = next_node
            return node

    def iterative(self, node: ListNode) -> ListNode:
        dummy_node = ListNode(0)
        dummy_node.next = node

        prev_node = dummy_node
        crnt_node = dummy_node.next
        while crnt_node:
            if crnt_node.val == self.__val:
                prev_node.next = crnt_node.next
                crnt_node = crnt_node.next
            else:
                prev_node = crnt_node
                crnt_node = crnt_node.next
        return dummy_node.next



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

remover = ElementRemover(1)
ret = remover.iterative(head)
# ret = remover.recursive(head)
printNodes(ret)

 

 

참조 : 코딩테스트, 초급, 여러 element삭제하기 (링크드리스트) - YouTube