[leetcode] 19. Remove Nth Node From End of List

문제 설명

링크
뒤에서 n번째 노드 제거하기

접근 1 - linked list 의 길이 구하기

• 길이(len) 을 구하여 len - n 번째와 len - n + 2 번째 이어주기

코드 1

    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        pointerA = pointerB = head
        length = 0

        while pointerB:
            length += 1 
            pointerB = pointerB.next
            
        if length == n:
            return head.next
        
        for _ in range(length - n - 1):
            pointerA = pointerA.next
            
        pointerA.next = pointerA.next.next
        return head

접근 2 - One pass (Two pointers)

• slow 와 fast 이용
• fast를 n 만큼 이동시켜놓은 이후 slow, fast 한칸씩 이동 > fast와 slow 간격 n 유지
• fast 가 맨 끝 노드에 다다르면 (fast.next == null) 지우기

코드 2

    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        fast = slow = head
        for _ in range(n):
            fast = fast.next
        if not fast:
            return head.next
        while fast.next:
            fast = fast.next
            slow = slow.next
        slow.next = slow.next.next
        return head