[leetcode] 19. Remove Nth Node From End of List

문제

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

 

풀이

어떤 node를 지우기 위해선 그 노드의 앞 node를 알아야한다.

head node는 앞 node가 없기 때문에, 임시로 prev node를 만들어서 앞에 붙여준다.

 

그 후, 두개의 포인터를 관리하는데, 서로 차이가 n+1만큼 떨어지게 관리한다.

이렇게 하면 앞쪽 포인터가 NULL에 도착했을 때, 뒷쪽포인터는 지워야할 node의 앞 node를 가리키게 된다.

따라서 뒷쪽포인터를 이용하여, 삭제작업을 진행하면 된다.

 

Time Complexity : $O(n)$

 

코드

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode * prev = new ListNode(0);
        prev->next=head;
        ListNode * n1= prev;
        ListNode * n2= prev;
        
        for(int i=0;i<=n;i++) n2=n2->next;
        while(n2)
        {
            n1=n1->next;
            n2=n2->next;
        }
        ListNode * d = n1->next;
        n1->next=n1->next->next;
        delete d;
        
        return prev->next;
    }
};