[LEETCODE] 19: Remove Nth Node From End of List(Python)

Remove Nth Node From End of List - LeetCode

문제 설명

단방향 연결 리스트가 주어질 때, 뒤에서 n번째 노드를 제거하고 연결 리스트의 head를 반환하는 문제이다.

나의 풀이

# 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]:
        cnt=0
        pointer=head
        while pointer!=None:
            pointer=pointer.next
            cnt+=1
        if cnt==1:
            head=None
            return head
        num=cnt-n
        if cnt==n:
            head=head.next
            return head
        
        pointer=head
        for i in range(num-1):
            head=head.next
        if n==1:
            head.next=None
        else:
            head.next=head.next.next
        head=pointer
        return head

자세한 설명은 이 글에 작성했다.

시간복잡도

전체 순회에 O(n), 삭제하려는 노드 탐색에 O(n)이 걸린다.