Leetcode Python - 19. Remove Nth Node From End of List

Leetcode #19 - Remove Nth Node From End of List

이번에는 특정 챕터별로 문제들을 풀어보겠습니다. linkedlist를 집중적으로 풀어보겠습니다.

리트코드의 문제 19 ‘Remove Nth Node From End of List’을 파이썬으로 풀어 보도록 하겠습니다.

discuss를 보도록 하겠습니다..

포인트는 head 앞에 dummy ListNode를 만드는 것입니다.

전체 코드는 아래와 같습니다.

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        dummy = ListNode(0)
        dummy.next = head
        
        slow = fast = dummy
        for _ in range(n):
            fast = fast.next
        
        while fast.next:
            slow = slow.next
            fast = fast.next
        slow.next = slow.next.next
            
        return dummy.next

시간복잡도는 O(n) : n개의 node를 방문

공간복잡도는 O(n) : n크기의 linked list를 만듦

dfs를 이용해 풀 수도 있습니다.

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if not root:
            return
        stack = [root]
        while stack:
            node = stack.pop()
            if node.left and node.right:
                node.left.next = node.right
                if node.next:
                    node.right.next = node.next.left
                stack.append(node.right)
                stack.append(node.left)
        return root

시간복잡도는 O(n) : node의 모든 값들을 방문

공간복잡도는 O(n) : stack에 최대 n/2 크기 list 생성