Intuition

최대로 나올 수 있는 Number of Nodes가 30개이기 때문에 연결 리스트를 순회하면서 각각의 Node를 포인터 배열에 저장해놓는다면, 원하는 위치의 Node를 지우는 작업은 $O(1)$에 수행할 수 있을 것이라 생각했다.

Approach

연결 리스트를 순회하며 각각의 node를 배열에 저장한다.

    struct ListNode* cur=head;
    struct ListNode* arr[30];

    int i=0;
    for (;cur!=NULL;i++,cur=cur->next) arr[i]=cur;

이제 뒤에서부터 n번째 node를 지우기만 해주면 끝이다. 기본적으로, arr[i-n-1]에 있는 node의 next를 arr[i-n+1]로 바꿔주면 끝이다.
그러나, 여기서 코너케이스가 발생한다.
첫번째, 원소가 한개밖에 없는 경우. 이 경우는 한 개의 원소를 지울 수 밖에 없기 때문에 결국 NULL값을 반환하게 된다.
두번째, index 0의 원소를 지우는 경우. 이 경우는 두번째 원소를 head로 삼아 반환하면 된다.
세번째, 가장 마지막 원소를 지우는 경우. 이 경우는 arr[i-n+1]이 애초에 없기 때문에 arr[i-n-1]의 다음 연결리스트를 NULL로 할당시켜주면 된다.
네번째, 이 경우가 가장 기본적인 중간 삭제의 경우다.

    if(i==1) return NULL;
    if (i-n==0) head=arr[1];
    else if (n==1) arr[i-n-1]->next=NULL;
    else arr[i-n-1]->next=arr[i-n+1];

    return head;

Solution

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
    struct ListNode* cur=head;
    struct ListNode* arr[30];

    int i=0;
    for (;cur!=NULL;i++,cur=cur->next) arr[i]=cur;

    if(i==1) return NULL;
    if (i-n==0) head=arr[1];
    else if (n==1) arr[i-n-1]->next=NULL;
    else arr[i-n-1]->next=arr[i-n+1];

    return head;
}

Complexity

Time Complexity

연결리스트를 한 번 순회하는 것 뿐이므로 $O(n)$

Space Complexity

마찬가지 이유로 $O(n)$

교수님 풀이

내 풀이는 마지막에 경우의 수를 네가지나 두게 되면서 깔끔하지 못한 느낌이 있다. 또한, 메모리 해제를 시켜주지 않았다.

Approach

교수님의 풀이는 투포인터를 사용한다. 풀이의 전체적 흐름은 아래와 같다.
두 포인터 $l$과 $r$의 간격을 $n$만큼 벌리고 그 간격을 유지한채로 $r$을 끝까지 보낸다. 그렇게 되면, $l$은 뒤에서부터 $n$번째에 위치한다.

포인터 두개를 head로 초기화시키고 메모리 해제를 위한 임시 포인터를 선언한다.

    listnode* left, *right, *temp;
    left=right=head;

포인터 $r$을 $n$만큼 뒤로 이동시켜서 두 포인터의 간격을 $n$만큼 벌려준다.$^{[1]}$
1 -> 2 -> 3 -> 4 -> 5       (n=2)
△          ▲                    ($l$:△, $r$:▲)

    while(n--) right=right->next;

그리고 $r$이 NULL이 될때까지 두 포인터를 옮겨보겠다.
1 -> 2 -> 3 -> 4 -> 5
                    △        ▲
우리가 4를 지우기 위해서는 3의 next를 5로 바꿔줘야하는데 $l$이 이미 4까지 와버린 이상 3에 접근할 수가 없게된다.
그래서 $r$->next가 NULL이 될때까지 두 포인터를 옮겨주어야한다.
1 -> 2 -> 3 -> 4 -> 5
             △           ▲

    while(right->next!=NULL){
        left=left->next;
        right=right->next;
    }

이제, 삭제하고자 하는 node의 메모리를 해제시켜주고, 이전 node를 다다음 node에 연결시켜준다.

    temp=left->next->next;
    free(left->next);
    left->next=temp;

    return head;

그런데 이렇게 풀이하게되면 앞서 포인터 $r$을 $n$만큼 뒤로 옮긴 과정$^{[1]}$에서 이미 $r$이 NULL이 되버린 코너케이스가 생긴다. 0번 index의 원소를 지우는 경우다.
1 -> 2 -> 3 -> 4 -> 5       (n=5)
△                             ▲
이 경우 $l$ 이 가리키는 node가 삭제 대상이 되고, $l$의 다음 node가 반환대상이 된다.

    if (!right){
        temp=left->next;
        free(left);
        return temp;
    }

Solution

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode listnode;

struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
    listnode* left, *right, *temp;
    left=right=head;

    while(n--) right=right->next;

    if (!right){
        temp=left->next;
        free(left);
        return temp;
    }

    while(right->next!=NULL){
        left=left->next;
        right=right->next;
    }

    temp=left->next->next;
    free(left->next);
    left->next=temp;

    return head;
}

Complexity

Time Complexity

$O(n)$

Space Complexity

$O(n)$

 

이 글의 Bonus Problem과 이어진다.

지적 및 질문 환영