[C] LeetCode 19. Remove Nth Node From End of List

문제(원문)

문제(번역)

주어진 Linked List head가 있을때, 뒤에서 부터 n번째 노드를 삭제해라.

단 Linked List 는 단방향이다.

 

이 문제를 1번에 풀 수 있는가?

접근 방법

Two pointer 기법을 사용하면 된다.

현재 노드를 가리키는 포인터와 n만큼 앞서가는 포인터를 두고 사용하면 된다.

앞서가는 포인터가 마지막 노드라면, 현재 노드가 자연스레 삭제될 노드가 되기 때문이다.

이와 함께 현재의 이전 노드를 저장할 포인터도 필요하다.

 

앞서가는 포인터가 마지막 노드에 도착했을때 현재 삭제할 노드가 중간에 있는 노드인지, head 원소인지 확인해야 한다.

우리는 원본 리스트를 그대로 반환할 것이기 때문에, head 노드가 삭제 대상이라면 head 노드를 head->next로 바꾸어주어야 한다.

삭제할 노드가 중간에 있다면 그냥 지워주면 된다.

소스 코드

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    struct ListNode *cur, *fin, *prev;
    cur = head; fin=head; prev = NULL;
    while(n--) fin = fin->next;
    while(fin) {
        if(fin->next == NULL) {
            if(prev) { // if middle
                prev->next = cur->next;
                free(cur);
            } else { // if first..
                prev = head;
                head = head->next;
                free(prev);
            }
            break;
        }
        cur = cur->next;
        fin = fin->next;
        prev = (prev) ? prev->next : head;
    }
    return head;
}

 

 

 

느낌 상 포인터를 2개로 줄이면 더 메모리를 최적화 할 수 있을 것 같다. 하지만 일단 이 풀이로도 만족한다.