[LeetCode] Remove Duplicates From A Sorted List

문제 링크

Remove Duplicates from Sorted List - LeetCode

Can you solve this real interview question? Remove Duplicates from Sorted List - Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well. Example 1: [https://assets.leetcode.com/uploads/2021/01/04/list1.jpg] Input: head = [1,1,2] Output: [1,2] Example 2: [https://assets.leetcode.com/uploads/2021/01/04/list2.jpg] Input: head = [1,1,2,3,3] Output: [1,2,3] Constraints: * The number of nodes in the list is in the range [0, 300]. * -100 <= Node.val <= 100 * The list is guaranteed to be sorted in ascending order.

https://leetcode.com/problems/remove-duplicates-from-sorted-list/

문제 요구 조건

linkedList을 인자로 받아요

오름차순으로 정렬되어 있지만 중복된 값이 존재해요

중복을 제거한 linkedList를 반환해야돼요!

나의 문제 풀이

linkedList가 어떻게 다루어져야되는지 코드에 대한 이해부족으로 아예 풀지 못했어요 ㅠ 풀이로 바로 가실게요.

정답 문제 풀이

일단 이 문제를 풀기위해서는 linkedList에 대한 이해와 javascript에서 어떻게 linkedList를 다루는지 알아야해요. 하지만 javascript에서는 linkedList를 직접 생성하고 사용하는 기본 문법이나 객체가 제공되지 않아요. LinkedList는 자바스크립트의 기분 자료구조가 아니기 때문이죠.

그래서 제공된 문제의 상단에 보면 LeetCode에서 어떻게 linkedList를 정의해야 되는지 설명이 되어있어요.

문제 상단에 listNode에 대한 구조 제공

설명을 보면 listNode는 val이라는 현재값과 next라는 포인터가 제공이 된다는 것을 알 수있네요. 제가 문제를 유심히 보지 않아서 이 부분을 제대로 읽어보지 못했네요 ㅠ 자바스크립트의 linkedList구조를 몰라서 아예 풀 수가 없었거든요.

그럼 이 지식에서부터 문제를 풀 수 있어요.

정답 풀이

JavaScript

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 * this.val = (val===undefined ? 0 : val)
 * this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function(head) {
    // 리스트가 비어 있거나 노드가 하나뿐인 경우를 처리
    if (!head || !head.next) {
        return head;
    }

    let current = head;

    while (current && current.next) {
        // 중복 노드 확인
        if (current.val === current.next.val) {
            // 중복이 발견되면 다음 노드를 건너뜀
            current.next = current.next.next;
        } else {
            // 중복이 아니면 다음 노드로 이동
            current = current.next;
        }
    }

    return head;
};

일단 head가 null이거나 head.next가 null인 경우를 먼저 확인해요. 여기서 리스트가 비어있거나, 노두가 하나뿐인 경우를 체크할 수 있죠.

head를 current에 할당하면서 초기 포인터를 세팅해요.

while루프를 상요해서 current와 current.next가 존재하는 동안 순회하도록 해요

현재 노드의 값 val과 다음 노드의 값 next.val 이 같을 경우에 다다음 노드를 다음노드에 할당하면서 중복을 제거해요.

같지 않다면 다음 노드를 current에 할당해서 순회하도록 해요.

마지막으로 current가 아닌 head를 반환합니다.

왜냐하면 current는 순회하면서 계속 이동하는 포인터이기 때문이에요. 따라서 current를 반환하면 마지막 순회시점의 노드를 반환하게 되요. head는 전체 리스트의 첫 번째 노드를 가리키는 포인터이기 때문에 순회하며 중복이 제거된 linkedList를 그대로 반환하게 되어요.

느낀점

LinkedList문제를 풀 때는 listNode를 어떻게 정의하는 지 꼭 확인해야 겠다고 생각했어요.