[ leetcode 문제풀이 ] Remove Nth Node From End of List

Remove Nth Node From End of List - LeetCode

Remove Nth Node From End of List - LeetCode

(Remove Nth Node From End of List 문제는 위 링크에서 풀어보실 수 있습니다.)

 

 

 

< Remove Nth Node From End of List 문제 설명 >

 

Remove Nth Node From End of List 문제는 다음과 같다.

Given the head of a linked list, remove the nth node from the end of the list and return its head.

 

Linked List의 head가 주어질 때 뒤에서부터 n번째 노드를 제거하고 head를 리턴하여라.

 

다음 세 가지 출력 예시가 주어졌다.

 

 

주어진 제한 조건은 다음과 같다:

linked list의 노드 개수는 sz 이다.

1  ≤  sz  ≤  30

0  ≤  Node.val  ≤  100

1  ≤  n  ≤  sz

 

Follow up question: one pass로 구현하여라.

 

 

---

< Remove Nth Node From End of List 문제 접근 >

 

이 문제를 one pass로 풀 수 있는 방법은 바로 delayed pointer을 사용하는 것이다. 

말은 거창하게 소개를 했지만그냥 주어진 n에 대해서 현재 노드보다 n만큼 뒤의 노드를 가리키도록 하는 포인터를 사용하는 것이다. 그러면 현재 노드가 linked list의 끝에 다달았을 때 delayed pointer에서 삭제 작업을 해주면 되는 것이다.

 

이를 구현한 알고리즘은 다음과 같다. (Cpp 사용)

 

ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode *pointNode = head, *pointDelayedNode = head;
    while(n--) pointNode = pointNode->next;
        
    if(pointNode == nullptr) return head->next;
    while(pointNode->next != nullptr){
        pointNode = pointNode->next;
        pointDelayedNode = pointDelayedNode->next;
    }
    pointDelayedNode->next = (pointDelayedNode->next)->next;
        
    return head;
} // runtime : 4 ms (faster than 79.31 %), memory usage : 10.8 MB (less than 33.67 %)

 

맨 처음에 pointNode만 이동시킨 후 if문을 적용한 이유는 만약 pointNode가 nullptr를 가리킨다면 이는 linked list의 head를 제거하라는 뜻이기 때문에 head->next를 head로 해서 리턴하면 된다.

 

pointNode == nullptr가 된 순간 pointDelayedNode는 삭제해야하는 노드의 바로 이전 노드이다. 따라서, pointDelayedNode의 next node만 수정해주면 된다.