LeetCode - Remove Nth Node From End of List

wodnr_P·2023년 9월 22일

Remove Nth Node From End of List leetcode linked list 알고리즘

LeetCode Top Interview 150

목록 보기

18/32

⭐️ LeetCode 알고리즘 풀이 (with Python)

# Remove Nth Node From End of List

[Quetion]

LeetCode 19. Remove Nth Node From End of List

📌 접근법

[문제 이해]

단일 Linked List의 끝에서 n번째 노드를 삭제한 Linked List 반환

끝에서 n번째 노드를 삭제하기 위해서는 마지막 노드를 알아야한다.

문제에서 주어진 Linked List는 데이터와 다음 노드를 가리키는 next 포인터밖에 없는 구조이기 때문에 마지막 노드를 찾기 위해서는 O(n)의 시간복잡도를 가지게 되므로 최대 O(n)을 기준으로 잡고 고민을 해보았다.

다음과 같은 생각의 흐름대로 구현을 시도했다.

Linked List의 데이터들을 리스트에 담는다
끝에서 n번째에 해당하는 데이터를 삭제한다 [O(1)]
리스트에 담긴 데이터를 다시 노드로 만든다
queue 자료구조를 활용하여 노드들을 다시 Linked List가 될 수 있게 연결해준다

💻 구현

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
    	# node 데이터를 담을 list
        dummy = []
        while head:
            dummy.append(head.val)
            head = head.next
        
        # 끝에서 n번째 데이터 삭제
        dummy.pop(-n)
        
        # 데이터가 없다면 빈 값을 리턴
        if not dummy:
            return 
        
        # list 데이터로 노드 생성
        for i in range(len(dummy)):
            dummy[i] = ListNode(dummy[i])
        
        # 새로운 노드를 만들고, 노드들을 다시 연결
        from collections import deque
        queue = deque(dummy)
        result = queue.popleft()
        curr = result
        
        while queue:
            node = queue.popleft()
            curr.next = node
            curr = node 
        return result

Runtime: 35ms | Memory: 16.3MB
LeetCode 코드 중 Runtime 89%, Memory 64% 해당하는 결과

📌 로직 핵심

tail이 있는 구조의 Linked List라면 마지막 노드를 찾기 까지 O(1)의 시간복잡도를 가지지만 그렇지 않기 때문에, 끝에서 n번째의 노드를 쉽게 삭제하기 위해 노드의 데이터들을 리스트에 담고 원하는 값을 삭제했다.
리스트에 담은 데이터를 다시 Linked List로 만들어 줌.
로직의 이해를 돕기 위한 그림은 다음과 같다.

📝 Remove Nth Node From End of List 회고

해당 코드의 시간복잡도는 O(N), 공간 복잡도는 O(N)이다.
루프를 순회하며 Linked List의 데이터를 담고, 데이터를 다시 Node로 만들면서 O(N)의 시간이 소요된 것이다.
list에는 Linked List의 순서대로 데이터가 담겨 있기 때문에, 리스트의 앞에서 부터 데이터를 가져와야 했으므로 deque의 popleft 연산을 활용했다. insert(0)도 있지만 insert(0)은 배열의 특성상 O(n)의 시간이 소요되므로 배제했다.
다른 솔루션도 확인해보니 포인터 두개를 사용하는 토끼와 거북이 알고리즘을 활용하여 해결한 코드들이 대부분이었다.

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        slow, fast = head, head
        
        while n > 0:
            fast = fast.next
            n -= 1
            
        while fast and fast.next:
            slow = slow.next
            fast = fast.next
            
        if fast:
            slow.next = slow.next.next
        else:
            head = head.next
        return head