19. Remove Nth Node From End of List

19. Remove Nth Node From End of List

 

# 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