Удаление повторяющихся элементов из отсортированного односвязного списка

Условие

Дан отсортированный односвязный список. Требуется избавиться от всех повторяющихся узлов так, чтобы каждый значение встречалось лишь один раз. Необходимо вернуть получившийся список, сохранив исходный порядок элементов.

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

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

/**
 * 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) {

    }
}

Ответ

Сравнивайте соседние узлы. Если значения равны, исключайте следующий узел из цепочки; иначе переходите дальше. Благодаря сортировке все повторы расположены подряд.

public ListNode deleteDuplicates(ListNode head) {
    ListNode current = head;
    while (current != null && current.next != null) {
        if (current.val == current.next.val)
            current.next = current.next.next;
        else
            current = current.next;
    }
    return head;
}

Время O(n), дополнительная память O(1). Исходный список изменяется, новые узлы не создаются. При удалении current не сдвигается, чтобы проверить длинную цепочку одинаковых значений. Пустой список и список из одного узла возвращаются без изменений.