(Easy - Fast & Slow Pointers) Leetcode - 203. Remove Linked List Elements

이 문제는 Linked-List에서 원하는 값을 전부 삭제해야하는 문제입니다.

 

찾는 값이 리스트 중간에 있는 경우 이전 노드의 next를 다음 노드에 연결한 다음 현재 노드를 삭제합니다.

즉, 이전 노드를 추적하는 포인터가 필요합니다.

또한, 만약 찾는 값이 중간이 아닌 맨 앞에 있으면 이전 노드를 추적할 필요 없이 head를 다음 노드로 만들고 맨 앞 노드였던 노드를 삭제해줍니다.

 

이렇게 두 과정을 차례대로 진행해주면 되는데 먼저 맨 앞에 있는 경우를 처리하고 리스트 중간에 있는 경우를 처리해주면 됩니다.

 

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        if (!head) return nullptr;
		
        // 만약 찾는 값이 Linked-List의 맨 앞에 있다면
        while (head && head->val == val) {
            ListNode* temp = head; // 임시로 저장
            head = head->next; // 다음 노드가 head가 된다.
            delete temp; // 임시로 저장한 노드 삭제
        }

        ListNode* cur = head;
        ListNode* pre = nullptr; // 이전 노드 추적
        while (cur) {
            if (cur->val == val) { // 찾는 값을 가진 노드를 찾았다면
                pre->next = cur->next; // 이전 노드의 next에 다음 노드를 연결
                delete cur; // 현재 노드를 삭제
                cur = pre->next; // 현재 노드 갱신
            }
            else {
                pre = cur;
                cur = cur->next;
            }
        }

        return head;
    }
};