📝 LeetCode 19 풀이

---

💡문제 정의

LeetCode 19 << 링크
19번 문제는 단일 연결 리스트(Singlt Likned List) 및 Two Pointers 관련 문제다.

단일 연결 리스트의 head가 주어졌을 때, 뒤에서 n번째 노드를 삭제한 후의 리스트를 반환해야 한다.

리스트의 길이(노드의 개수)와 각 노드의 값은 위와 같다.

---

💡풀이

1-1) C

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

struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
    int len = 0, move;
    struct ListNode *cur, *before;
    struct ListNode *temp = head;

    while (temp != NULL) {
        len++;
        temp = temp->next;
    }

    if (n == len) {
        temp = head->next;
        free(head);
        return temp;
    }

    move = len - n;
    before = head;

    for (int i = 0;i < move - 1;i++) {
        before = before->next; // before becomes (k-1)th node
    }

    cur = before->next; // cur becomes kth node
    temp = cur->next; // temp becomes (k+1)th node
    free(cur);
    before->next = temp;
    
    return head;
}

나의 해법은 아래와 같다.

1. 연결 리스트의 길이(len)를 구한다.
2. 리스트의 맨 앞에서 len - n(move)만큼 이동하여 k번째 노드를 삭제한다. (k-1번째 노드와 k+1번째 노드를 연결)

주의 할 점은 head(맨 앞 노드)를 삭제할 때, 즉 n == len인 경우이다. 이 경우 len - n의 값이 0이 되고, 위 코드에서 before 노드를 정의할 수 없게 된다.
따라서 if문을 통해 이 케이스를 예외적으로 처리한다. 단순히 head를 한 칸 옮긴 후 바로 return하면 된다.

1-2) C

1-1은
1. 리스트의 길이를 구할 때
2. 다시 for문을 이용해 뒤에서 n번째 노드(삭제할 노드)까지 갈 때
-> 전체 리스트를 총 2번 scan해야 한다.

Two Pointers를 이용하면 전체 단일 연결 리스트를 한 번만 scan하여 문제를 해결할 수 있다.
여기서 투 포인터란? 1차원 배열에서 두 개의 포인터를 조작하여 원하는 결과를 얻는 알고리즘을 말한다. 이 문제에서는 left와 right 포인터를 각각 조작하여 뒤에서 n번째 노드를 삭제한다.

1. left와 right 포인터를 정의
2. right 포인터를 head에서 시작하여 n번 이동
3. left와 right 사이에는 n개의 노드가 존재하게 됨
4. right 포인터가 NULL이 될 때까지, left와 right을 동시에 한 칸씩 이동
5. left 포인터가 가리키는 노드 제거

그런데 위와 같이 코드를 구현하면 문제가 발생한다. 우리는 left의 previous 노드를 left의 next 노드와 연결해야 하기 때문. 따라서 아래와 같이 구현하면 된다.

1. left와 right 포인터를 정의
2. right 포인터를 head에서 시작하여 n번 이동
3. left와 right 사이에는 n개의 노드가 존재하게 됨
4. right 포인터의 next가 NULL이 될 때까지, left와 right을 동시에 한 칸씩 이동
5. left 포인터의 next가 가리키는 노드 제거

Two Pointers를 이용한 코드는 아래와 같다.

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

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

    left = right = head;
    for (int i = 0;i < n;i++)
        right = right->next;

    if (!right) { // if right is NULL (n==length of list)
        struct ListNode *temp = head->next;
        free(head);
        return temp;
    }

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

    struct ListNode *temp = left->next->next;
    free(left->next);
    left->next = temp;
    
    return head;
}

---

💡참고

https://ssungkang.tistory.com/entry/Algorithm-Two-Pointers-%ED%88%AC-%ED%8F%AC%EC%9D%B8%ED%84%B0