[LeetCode] 2487. Remove Nodes From Linked List

I. Description

문제 링크: https://leetcode.com/problems/remove-nodes-from-linked-list/description/?envType=problem-list-v2&envId=stack

---

II. Code

i)

# # Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
        stack = []
        current = head
        
        while current:
            while stack and stack[-1] < current.val:
                stack.pop()
            stack.append(current.val)
            current = current.next
            
        dummy = ListNode(0)
        current = dummy
        for val in stack:
            current.next = ListNode(val)
            current = current.next
            
        return dummy.next

처음에 생각한 방법은 Linked List의 앞부터 차례로 확인하며 뒤까지 오는 방식이다. 시간복잡도는 O(n)이다.

 

ii)

# # Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # If linked list is empty of has only one node
        if head is None or head.next is None:
            return head
            
        next_node = self.removeNodes(head.next)
            
        # If next node has greater value than head, delete the head
        if head.val < next_node.val:
            return next_node
          
        # Otherwise, keep the head  
        head.next = next_node
        return head

Recursion을 사용하여 푸는 방식이다. 같은 방식을 반복할 때 recursion을 한 번 생각해봐도 되겠다. 값을 꺼낼 때 효율적인 방법인 stack을 동시에 활용했다. 시간복잡도는 O(n)이다.

 

iii)

# # Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverse_list(self, head):
        prev = None
        current = head
        next_temp = None
        
        while current:
            next_temp = current.next
            current.next = prev
            prev = current
            current = next_temp
            
        return prev
            
    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
        head = self.reverse_list(head)
            
        maximum = 0
        prev = None
        current = head
        
        while current:
            maximum = max(maximum, current.val)
            
            if current.val < maximum:
                prev.next = current.next
                current = current.next
            else:
                prev = current
                current = current.next
        
        return self.reverse_list(head)

Reverse 원리

뒤부터 하면 maximum 값만 계산하며 node를 제거해가며 되기 때문에 Linked List의 뒤부터 앞으로 확인하는 방식을 생각할 수 있다. 이때 reverse를 활용하면 더 쉬워지겠다. Reverse할 때도 연결관계만 바꾸면 되는 Linked List의 특성 때문에 간단하게 가능하다. 시간복잡도는 O(n)이다.

 

실패 케이스도 있었다.

iV)

# # Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0)
        dummy.next = head
        current = dummy
        
        while current.next:
            runner = current.next.next
            must_remove = False
            
            while runner:
                if runner.val > current.next.val:
                    must_remove = True
                    break
                runner = runner.next
            
            if must_remove:
                current.next = current.next.next
            else:
                current = current.next
                
        return dummy.next

처음에는 마치 2개의 포인터를 사용하는 것처럼 확인하는 방식을 생각했다. 그러나 이렇게 하면 시간복잡도가 O(n^2)이 되어 Time Limit Exceeded 에러가 발생했다.