[LeetCode 해석 및 풀이] 19. Remove Nth Node From End of List

LeetCode 문제 해석 및 풀이 방법

 

문제 19. Remove Nth Node From End of List(리스트 뒤에서 N번째 노드 없애기)

바로가기

 

문제 설명

영문

Given the head of a linked list, remove the nth node from the end of the list and return its head.

Follow up: Could you do this in one pass?

 

한글

연결 리스트의 head가 주어지면, 뒤에서 n번째 노드를 제거하고 head를 반환하십시오.

 

제한조건

• The number of nodes in the list is sz.
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

 

입출력 예

입력	출력
head = [1,2,3,4,5], n = 2	[1,2,3,5]
head = [1], n = 1	[]
head = [1,2], n = 1	[1]

 

 

해답 및 해설

파이썬 (Python)

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        target_mother = None
        count = 0

        last_node = head
        while last_node:
            last_node = last_node.next
            if count == n:
                target_mother = head
            elif count > n:
                target_mother = target_mother.next
            count += 1

        if not target_mother: return head.next

        target_mother.next = target_mother.next.next

        return head

지워야 하는 타겟의 부모모드를 찾도록 한다. 찾는 방법은 원소 갯수를 세다가 n개가 나오면 그때부터 끝노드를 찾는 노드와 병행하게 다음 노드를 찾도록 이동 시킨다.

타겟의 부모모드를 못 찾았으면, 타겟이 첫 노드란 뜻이므로 현재 head의 다음 노드를 반환하고, 아니라면 타겟노드를 삭제한 후 현재 head를 반환한다.