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

Description

정렬된 링크드 리스트에서 중복되는 값을 가진 노드를 제거하여 반환하는 문제입니다.

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.

Example 1:

Input: head = [1,2,3,3,4,4,5]
Output: [1,2,5]

Example 2:

Input: head = [1,1,1,2,3]
Output: [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. Two pointers

public ListNode deleteDuplicates(ListNode head) {

    ListNode dHead = new ListNode(-1);
    dHead.next = head;
    ListNode prev = dHead;
    ListNode cur = head;
    while(cur != null){

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

이전노드와 현재위치 2개의 포인터를 두고 현재숫자와 다음숫자가 달라질때까지 포인터를 전진시킵니다. 포인터가 전진하지 않은경우 이전노드를 그대로 한칸 전진시키고 중복값이 있어 포인터가 전진한 경우는 prev의 next에 이동한 노드의 다음 새로운 노드를 붙여줍니다.

Reference

Remove Duplicates from Sorted List II - LeetCode