[LeetCode | Javascript] - Remove Duplicates from Sorted List ||

문제

Linked List

• Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well.

82. Remove Duplicates from Sorted List II

• 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 = head.next.next;

    return deleteDuplicates(head);
  } else {
    head.next = deleteDuplicates(head.next);
    return head;
  }
};

첫 번째 풀이는 중복된 노드가 연속된 경우를 생각하지 못하고 푼 풀이이다.
예를 들어 [1, 1, 1, 2, 3] 같은 경우 [1,2,3]이 아니라 [2,3]이 출력되어야 한다.

정답 풀이

/**
 * 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) {
    // 다음 노드가 있는지 확인 && 현재 노드의 값과 다음노드의 값이 같으면 계속 반복 (중복된 노드를 건너뛰기 위한 조건)
    while (head.next !== null && head.val === head.next.val) {
      head = head.next;
    }
    return deleteDuplicates(head.next);
  } else {
    head.next = deleteDuplicates(head.next);
    return head;
  }
};

수정된 코드로는 중복된 노드가 있을 경우 현재 노드의 값과 다음 노드의 값이 같지 않을 때까지 현재 노드를 다음 노드로 이동시키고, 재귀함수로 다음 노드를 넘겨줌으로써 중복을 처리하는 식으로 풀었다.

• 실행 시간 : 61ms
• 메모리 : 50.8MB

다른 분 풀이

/**
 * 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) {
    const dummy = new ListNode();
    dummy.next = head;
    let node = dummy; 
  // 연결 리스트를 끝까지 순회
    while (node.next) {
      // 다음 노드와 그 다음 노드가 존재하는지 확인 &&  현재 노드와 다음 노드의 값이 같은지 확인
        if (node.next.next && node.next.val === node.next.next.val) { 
          //  중복이 끝난 지점 이후의 첫 번째 다른 값의 노드를 찾기 위해 사용
            let nonValNode = node.next.next.next;
          
          // 현재 노드의 다음 노드(node.next.next.next)의 값과 같을 때 계속해서 nonValNode를 이동시킴
            while (nonValNode && nonValNode.val === node.next.val) {   
                nonValNode = nonValNode.next; // node.next.next.next.next
            }
          // 반복문에서 빠져나오면 nonValNode는 반복이 끝난 지점 바로 이후 노드이다.
            node.next = nonValNode;                                    
        } else {
            // 중복이 없으면 다음 노드로 이동
            node = node.next;                                         
        }
    }
    return dummy.next;
};

다른 분 풀이를 살펴보면 먼저 중복이 끝난 지점 이후의 첫 번째 다른 값의 노드를 찾기 위해 사용하기 위해 nonValNode변수에 node.next.next.next를 지정하고, nonValNode의 값과 현재 값이 중복된 값인지 확인하고 중복된 값이면 nonValNode를 nonValNode의 다음 노드로 이동시킨다.
이를 통해 while (nonValNode && nonValNode.val === node.next.val) 반복을 빠져나오면 node.next = nonValNode 를 실행한다.
nonValNode(첫 번째 다른 값의 노드)를 node.next로 지정해 중복된 노드를 건너뛰게 한다.

• 실행 시간 : 46ms
• 메모리 : 51.3MB