[LeetCode]Remove Nth Node From End of List

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

Remove Nth Node From End of List - LeetCode

 

문제 분석

주어진 링크드 리스트에서 뒤에서 n번째에 해당하는 노드를 제거하는 문제입니다.

 

처음 시도한 답안

접근 방법

# 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 = head
        # right를 미리 n칸 만큼 앞으로 전진
        # 이렇게 되면 right가 끝까지 가는 경우, left의 다음 노드가 삭제 대상으로 간주 가능.
        for _ in range(n):
            right = right.next
        
        # right가 없는 노드라면(n이 링크드 리스트 길이인 경우) 맨 처음 노드가 삭제 대상.
        if not right:
            return left.next
        
        while right.next:
            left = left.next
            right = right.next
        # right가 끝까지 도달하면, left의 다음 노드가 삭제 대상임.
        left.next = left.next.next

        return head

1. left, right 투 포인터를 활용합니다.
2. right 포인터를 미리 n 칸만큼 전진시킵니다. 
3. 만약 right 노드가 비어있다면 맨 처음 노드가 삭제 대상입니다.
4. right가 끝에 도달할 때까지, left, right를 한칸씩 이동합니다.
5. right가 끝에 도달하면 left의 다음 노드가 삭제 대상이 됩니다. 
6. next.next를 이용해 삭제 대상 노드를 제거합니다.

느리게가는 left 포인터, 미리 n칸 전진해있는 right 포인터를 활용해 One Pass로 문제를 해결할 수 있습니다.