[leetcode 19] 리스트의 끝에서 N번째 노드 삭제하기

링크드리스트의 head가 주어졌을때 끝에서부터 n번째 노드를 삭제하시오. 

 

ex1 ) head = [1,2,3,4,5], n = 2

 

 

풀이법

그냥 풀면 어렵고 링크드리스트의 길이를 구한다음 풀면 쉽다. 

- 링크드리스트의 길이를 구하고 그 길이를 L 이라고 하자. 

- 그러면 삭제해야하는 노드는 L - n 번째의 노드가 된다. 

- L - n 번째노드를 L - n + 2 노드와 교체하면 끝

 

풀이

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        
        dummy = ListNode(0)
        dummy.next = head
        
        first = head
        L = 0
        while first:
            L += 1
            first = first.next
        
        L -= n
        
        first = dummy
        
        while L > 0:
            L -= 1
            first = first.next
            
        first.next = first.next.next
        return dummy.next

 

위 풀이에서 dummy 노드가 있는 경우는, node가 1개인 경우 에러가 날 수 있으므로 엣지케이스를 방지하기 위해 추가한 것이다.