[leetcode #82] Remove Duplicates from Sorted List II

Problem

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.

Idea

주어진 List에서 중복 등장하는 노드를 없애는 문제다.

중복을 확인하기 위해 prev와 current, 그리고 dummy 노드를 만든다.
dummy 노드는 head 노드를 가리키는 포인터로 최종 결과를 리턴하기 위한 포인터다.
prev 노드는 current 노드 바로 뒤에 있는 노드로 중복이 발견되었을 때 중복된 노드 다음을 가리키도록 한다.

current 노드는 List 내 노드를 탐색하면서 중복이 발견되면 중복된 다음 노드를 건너뛰는 방식으로 중복 노드를 삭제한다. 중복 노드 삭제를 완료한 뒤 하나 남은 노드는 다음 iteration에서 prev 노드의 next 포인터가 current 노드의 next 포인터를 가리키도록 하면 된다.

iteration이 끝난 뒤 끝 부분이 중복이 되었을 수 있으므로 중복이 확인되면 prev의 next 포인터가 null을 가리키게 하여 마지막 남은 중복 노드를 제거한다.

Time Complexity: O(n)
Space Complexity: O(1)

Solution

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        boolean theSame = false;
        ListNode dummy = new ListNode();
        dummy.next = head;

        ListNode prev = dummy;
        ListNode current = head;

        while (current.next != null) {
            if (current.val == current.next.val) {
                current.next = current.next.next;
                theSame = true;
                continue;
            }

            if (theSame) {
                prev.next = current.next;
                theSame = false;
            } else {
                prev = prev.next;
            }

            current = current.next;
        }

        if (theSame) {
            prev.next = null;
        }

        return dummy.next;
    }
}

Reference

https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/