[Linked List][Medium] 19. Remove Nth Node From End of List

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

 

 

Q. 단일 리스트에서 뒤에서 n 번째 노드를 찾아 제거하여라. 

 

 

Solution. 

 우선 단일 리스트에서 뒤에서 n 번째 노드를 어떻게 찾는가. 

 노드 두개를 가지고 하나를 먼저 출발시킨다. (fastNode)

 이 노드가 앞에서 n번째 진행하면, 그 후에 다음 노드를 head에 둔다.(slowNode)

 fastNode가 리스트에 끝에 도달할 때까지 두 노드를 하나씩 진행 시킨다. 

 이 결과, slowNode가 바로 뒤에서 n 번째 노드가 된다. 

 이제 이 slowNode만 삭제하면 되겠다. 

 우리가 앞에서 부터 진행하므로, slowNode의 바로 앞노드를 알 수 있다.(prevNode)

 이 prevNode의 next를 slowNode의 next node로 설정하면, 결과적으로 slowNode가 지워지게 될 것이다. 

 여기에 헤드나 길이에 대해서 조금 예외처리를 한다. 

 

 

 

C#

public ListNode RemoveNthFromEnd(ListNode head, int n) 
{
    // find the target. 
    ListNode fast = head;
    ListNode slow = null;
    ListNode prev = null;
    int i = 1;
    while(fast != null)
    {
        if(slow != null)
        {
            prev = slow;
            slow = slow.next;
        }
        if(i == n)
            slow = head;

        ++i;
        fast = fast.next;
    }

    if(prev != null)
        prev.next = slow==null ? null : slow.next;
    else 
        head = slow==null ? null : slow.next;

    return head;
}

뒤에서 n 노드를 찾는 방법을 알면, 그렇게 복잡한 문제는 아니게 된다. 

 

결과.