(Easy - Fast & Slow Pointers) Leetcode - 83. Remove Duplicates from Sorted List

정렬된 Linked-List가 주어질 때 중복된 값을 가진 노드들을 삭제하는 문제입니다.

 

만약 다음(next) 노드가 현재 노드의 값과 같은 값을 가지면 두 노드는 중복된 것 입니다.

중복된 노드를 유일한 노드로 만들어야 하므로 다음 노드를 삭제하고 그 다음 노드에 현재 노드의 next를 연결합니다.

이 과정을 List의 끝까지 반복하면 중복된 노드들을 지울 수 있습니다.

 

/**
 * 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* deleteDuplicates(ListNode* head) {
        if (!head || !head->next) return head; // 만약 List가 비어있거나 Node가 하나뿐이라면

        ListNode* cur = head;
        while (cur) {
            ListNode* next = cur->next;
            // 다음 노드가 현재 노드와 같은 값을 가지고 있다면 (중복)
            if (next && cur->val == next->val) {
                cur->next = next->next; // 현재 노드를 그 다음 노드에 연결
                delete next; // 다음 노드 삭제
            }
            else
                cur = next;
        }

        return head;
    }
};