План курса / Все задачи / Алгоритмы и структуры данных
Удаление дубликатов из списка
легко
# решено
Дан указатель на голову отсортированного односвязного списка head. Нужно удалить все дубликаты, чтобы каждый элемент встречался только один раз и вернуть голову измененного списка.
Пример 1:
Ввод: head = [10,13,13,16]
Вывод: [10,13,16]
Пример 2:
Ввод: head = [4,4,4,4]
Вывод: [4]
Ограничения:
len(head) >= 1
/**
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int val, ListNode next=null) {
* this.val = val;
* this.next = next;
* }
* }
*/
public class Solution {
public static ListNode DeleteDuplicates(ListNode head) {
// сохраняем указатель на начало списка
ListNode result = head;
while (head != null && head.next != null) {
// если значения совпадают, пропускаем следующий узел
if (head.val == head.next.val) {
head.next = head.next.next;
} else {
head = head.next;
}
}
return result;
}
}
#include <vector>
using namespace std;
/**
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
ListNode* deleteDuplicates(ListNode* head) {
// сохраняем указатель на начало списка
ListNode* result = head;
while (head != nullptr && head->next != nullptr) {
// если значения совпадают, пропускаем следующий узел
if (head->val == head->next->val) {
head->next = head->next->next;
} else {
head = head->next;
}
}
return result;
}
package main
/**
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func deleteDuplicates(head *ListNode) *ListNode {
// сохраняем указатель на начало списка
result := head
for head != nil && head.Next != nil {
// если значения совпадают, пропускаем следующий узел
if head.Val == head.Next.Val {
head.Next = head.Next.Next
} else {
head = head.Next
}
}
return result
}
import java.util.*;
/**
* class ListNode {
* Integer val;
* ListNode next;
* ListNode() {}
* ListNode(Integer val) { this.val = val; }
* ListNode(Integer val, ListNode next) {
* this.val = val;
* this.next = next;
* }
* }
*/
public class Solution {
public static ListNode deleteDuplicates(ListNode head) {
// сохраняем указатель на начало списка
ListNode result = head;
while (head != null && head.next != null) {
// если значения совпадают, пропускаем следующий узел
if (head.val.equals(head.next.val)) {
head.next = head.next.next;
} else {
head = head.next;
}
}
return result;
}
}
from list_node import ListNode
# class ListNode:
# def __init__(self, val, next=None):
# self.val = val
# self.next = next
def delete_duplicates(head: Optional[ListNode]) -> Optional[ListNode]:
# сохраняем указатель на начало списка
result = head
while head and head.next:
# если значения совпадают, пропускаем следующий узел
if head.val == head.next.val:
head.next = head.next.next
else:
head = head.next
return result
import { ListNode } from './listNode.js';
/**
* class ListNode {
* constructor(val, next) {
* this.val = val;
* this.next = (next === undefined ? null : next);
* }
* }
*/
/**
* @param {ListNode} head
* @returns {ListNode}
*/
export function deleteDuplicates(head) {
// сохраняем указатель на начало списка
let result = head;
while (head !== null && head.next !== null) {
// если значения совпадают, пропускаем следующий узел
if (head.val === head.next.val) {
head.next = head.next.next;
} else {
head = head.next;
}
}
return result;
}
Оценка сложности
Время: O(n), где n - количество узлов в списке head