[Algorithm] 연결 리스트를 이용한 알고리즘 문제풀이 (Remove Duplicates)

어제 연결 리스트에 대한 포스팅을 올렸으니, 리트코드에서도 연결 리스트와 관련한 문제를 풀어보는 게 좋겠다고 생각했다. 선택한 문제는 다음과 같다.

83. Remove Duplicates from Sorted List
Given a sorted linked list, delete all duplicates such that each element appear only once.

 

정렬된 연결 리스트가 주어졌을 때, 중복되는 값을 가진 요소를 삭제하여 각 요소가 한 번씩만 나오도록 하는 문제다. 예를 들어 연결 리스트의 값이 1-1-2-3으로 주어진다면 이를 1-2-3 으로 수정해주면 된다.

어제 포스팅에서도 잠시 언급했지만, 연결 리스트의 특징은 각 노드는 다음 노드의 주소값을 가지고 있다는 것이다. 그렇다면 노드를 추가, 혹은 삭제할 때에도 다음 노드의 주소값을 변경해주면 된다. (하단 이미지 참고)

이에 착안해서 아래와 같이 문제를 풀어보았다. 

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */

var deleteDuplicates = function(head) {
// 헤드가 null 이면 바로 헤드를 리턴
    if(head === null) return head;
// 현재 검색하는 노드를 nowNode라는 변수에 담는다. 시작은 물론 헤드부터.
    let nowNode = head;
// 다음 노드가 null일 때까지. 즉, 마지막 노드가 될 때 까지 반복문을 돌린다
    while(nowNode.next !== null){
    // 현재 노드의 값과 다음 노드의 값이 같다면, 현재 노드의 next 값을 다음 다음 노드로 변경한다
    // 그렇지 않을 경우 다음 노드로 넘어간다.
        if(nowNode.val === nowNode.next.val){
            nowNode.next = nowNode.next.next;
        } else {
           nowNode = nowNode.next;
        }
    }
    return head;
};

 

앞에서부터 순차적으로 노드를 훑어야 하므로 시간복잡도는 O(N)이 될 것이다.

clear!