복's

[ LeetCode - 19 ] Remove Nth Node From End of List 본문

알고리즘/LeetCode

[ LeetCode - 19 ] Remove Nth Node From End of List

나복이 2023. 10. 31. 08:23
728x90

https://leetcode.com/problems/remove-nth-node-from-end-of-list/description/

 

Remove Nth Node From End of List - LeetCode

Can you solve this real interview question? Remove Nth Node From End of List - Given the head of a linked list, remove the nth node from the end of the list and return its head.   Example 1: [https://assets.leetcode.com/uploads/2020/10/03/remove_ex1.jpg]

leetcode.com

다시 등장한 Linked List 문제다.

이번에는 순회 및 값 연산이 아니라 삭제 문제로 바라보고 있는 주소 값을 끊어주면 되는 문제다.

불편한 점은 IDE에서는 못하고, 사이트 내에서 풀어야 한다는거?


[ 📌 풀이 ]

가장 먼저 필요한게 삭제할 노드를 식별하는 것인데, 뒤에서 n번째 노드고, prev 없이 단 방향 next로만 순회하는 리스트이기 때문에 알기가 쉽지 않았다.

 

그래서 list를 한 번 순회하면서 size를 측정 후 해당 노드까지 이동하면서 이전 노드를 기억 했다가 이전 노드와 삭제할 노드의 다음 노드의 연결을 했다.


[ 📌 코드 - Python ]

"""
# Author    : Lee In Bok 
# Date      : 2023.10.31(Tue)
# Spend Time: 16m 29s
# Runtime   : 37 ms (Beats 77.38%)
# Memory    : 16.2 MB (Beats 44.62%)
# Algoritm  : Linked List
"""

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        size = 0
        temp, prev = head, None
        
        while temp:
            temp = temp.next
            size += 1

        temp = head

        for _ in range(size - n):
            prev = temp
            temp = temp.next

        if prev:
            prev.next = temp.next
        elif size >= 2:
            return temp.next
        else:
            return 

        return head

[ 📌 결과 ]

[ Result ]

728x90