19. Remove Nth Node From End of List ☆★★★★

19. Remove Nth Node From End of List

 

✅ 올바른 풀이 (Two Pointer 방식 권장)

아래는 리버스 없이 깔끔하게 해결할 수 있는 two pointer 방식입니다:

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        # 더미 노드 설정 (head 제거될 경우 대비)
        dummy = ListNode(0, head)
        fast = slow = dummy
        
        # fast를 n+1만큼 먼저 이동시켜서 간격 만들기
        # 왜? n 이동하고. dummy.next 부터 시작이니 1도 더함
        for _ in range(n + 1):
            fast = fast.next
        
        # fast와 slow를 함께 이동
        while fast:
            fast = fast.next
            slow = slow.next
        
        # slow.next가 제거 대상
        slow.next = slow.next.next
        
        return dummy.next

# 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]:
        """
        아이디어는. 투 포인터(left, right)를 사용하고
        right 포인터는 미리 n 만큼 먼저 shifting 한뒤.

        left, right 를 1개씩 shifting 하는데, 
        right 가 끝에 도달하면, left 는 삭제해야할 데이터에 있을테니, 삭제
        이때, left prev 가 필요한데, 그래서, left 를 left prev 처럼 활용하기!
        """
        dummy = ListNode(0, head) # dummy.next 가 head 임
        left = dummy # left 를 dummy.next 가 아닌, dummy로 세팅 (left prev 대신)
        right = head

        # right 를 n 만큼 shift
        while n > 0 and right:
            right = right.next
            n -= 1

        # left, right 둘다 shift
        while right:
            right = right.next
            left = left.next

        # left 삭제
        # L가 1 이 라면 : 1->2->3
        left.next = left.next.next # L가 1 이 라면 : 1->3
        return dummy.next

 

 

https://youtu.be/XVuQxVej6y8?si=s4ORl143hT4CLxvU