19. 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.

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

접근

#투 포인터 #연결리스트
포인터 두 개를 사용한다. 뒤에서 n번째라는 것은 즉 List Size - n만큼 전진했을 때와 같은 위치이므로, P1과 P2의 간격을 n으로 하고 P2가 리스트의 끝까지 전진했을 때 P1의 링크를 그 다음 노드와 연결한다.

코드

# 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]:
        
        tmp=ListNode(-1)
        tmp.next = head # 예외처리를 위해 -1인덱스의 값을 설정.
        
        
        p1 = tmp # 순회용 i번째 노드.
        p2 = tmp # i+n번째 노드. 이것은 i가 n번째일때 맨 끝을 가리키게 된다.
        
        for i in range(n):
            p2 = p2.next # p2를 i+n로 세팅

            
        while p2.next != None: # p2가 리스트 끝까지 갈 때까지 진행한다.
            p1 = p1.next
            p2 = p2.next
        
        p1.next = p1.next.next #중간의 링크를 끊는다.
        
        return tmp.next
        

효율성

시간복잡도 : O(N)

Runtime: 70 ms, faster than 16.71% of Python3 online submissions for Remove Nth Node From End of List.
Memory Usage: 13.8 MB, less than 70.33% of Python3 online submissions for Remove Nth Node From End of List.