[LeetCode] 83. Remove Duplicates from Sorted List - 문제풀이

Description

정렬된 LinkedList에서 중복된 값을 제외하고 연결하여 반환하는 문제입니다.

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:

Input: head = [1,1,2]
Output: [1,2]

Example 2:

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.

Solution 1. Iteration(반복)

public ListNode deleteDuplicates(ListNode head) {

    // 1. Iteration
    ListNode dHead = new ListNode(Integer.MIN_VALUE);
    ListNode cur = dHead;
    dHead.next = head;

    while(cur.next != null){
        if(cur.val == cur.next.val){
            cur.next = cur.next.next;
        }else{
            cur = cur.next;
        }
    }
    return dHead.next;
}

반복문과 포인터를 이용하여 LinkedList를 순회하면서 현재노드와 다음 노드의 값이 같은경우 현재노드의 다음노드를 다다음노드로 연결하고 당겨주고 아닐 경우 커서를 앞으로 한칸 이동시킵니다.

Solution 2. Recursion (재귀)

public ListNode deleteDuplicates(ListNode head) {

    // 2. Recursion
    if(head == null || head.next == null) return head;
    head.next = deleteDuplicates(head.next);
    if(head.val == head.next.val){
        return head.next;
    }else{
        return head;
    }
}

재귀호출을 이용한 방법입니다. 다음노드를 가지고 있는 노드까지 재귀호출을 통해 마지막노드 부터 채워 나갑니다. 호출 대상값과 다음 노드가 같다면 대상노드가 아닌 대상노드의 다음노드를 붙여 스킵해줍니다.

Reference

Remove Duplicates from Sorted List - LeetCode