[LeetCode | Javascript] - Remove Duplicates from Sorted List

문제

Linked 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.

83. Remove Duplicates from Sorted List

• 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.

문제 정리

이 문제는 각 요소가 한 번만 나타나도록 중복 항목을 제거해 연결 리스트를 반환하는 문제이다.

Solution

/**
 * 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 === null || head.next === null) {
        return head;
    }
    // 다음 노드의 값과 중복일 때
    if (head.val === head.next.val) {
        head.next = head.next.next;  // 다음 노드로 넘어감
        return deleteDuplicates(head); // 재귀함수를 이용해 다시 반복
    } else {
     //다음 노드의 값과 다를 때 다음으로 넘어가면서 중복확인
        head.next = deleteDuplicates(head.next);
        return head;
    }
};

필자는 현재 노드의 값(head.val)과 다음 노드의 값(head.next.val)이 같을 때 그냥 다음 노드(head.next)를 그다음 노드(head.next.next)로 변경하여 중복된 노드를 건너뛰게 구현하였다.
다음 노드로 변경을 하고 재귀 함수에 현재 노드를 넘겨줌으로써 다시 함수를 실행해 중복을 검사한다.
만약 중복이 없다면 다음 노드(head.next)를 재귀 함수에 넘겨주고 현재 노드(head)는 그대로 반환한다.

• 실행 시간 : 76ms
• 메모리 : 51.5MB

다른 분 풀이

/**
 * 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) return null;
    let prev = head, next = head.next;

    while (next) {
        if (prev.val === next.val) {
            prev.next = next.next;
        } else {
            prev = prev.next;
        }
    	next = next.next;
    }

    return head;
};

다른 분이 푸신 풀이도 비슷한 로직이지만 반복문을 사용해 중복된 노드를 처리하는 방식이다.
또 포인터를 명시해서 더 직관적으로 표현한 코드같다. 실행 시간도 더 빨랐다..👍

• 실행 시간 : 60ms
• 메모리 : 51.6MB