83. Remove Duplicates from Sorted List

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example, given 1->1->2, return 1->2. Given 1->1->2->3->3, return 1->2->3.

83. Удаление дублей из связного списка

Задан связный список. Удалите все дубли элементов. То есть каждый элемент должен встречаться только раз.

Например, по списку 1->1->2 верните 1->2. По списку 1->1->2->3->3 верните 1->2->3.

// C++

/**

* Definition for singly-linked list.

* struct ListNode {

* int val;

* ListNode *next;

* ListNode(int x) : val(x), next(NULL) {}

* };

*/

class Solution {

public:

ListNode* deleteDuplicates(ListNode* head) {

}

};

// Java

/**

* Definition for singly-linked list.

* class ListNode {

* int val;

* ListNode next;

* ListNode(int x) {

* val = x;

* next = null;

* }

* }

*/

public class Solution {

public ListNode deleteDuplicates(ListNode head) {

}

}

РЕШЕНИЕ

список

Анализ алгоритма

Идем по списку слева направо, пока он содержит хотя бы два элемента. Если текущий элемент равен следующему, то перебрасываем next указатель текущего элемента на элемент за следующим.

Реализация алгоритма

class Solution

{

public:

ListNode* deleteDuplicates(ListNode* head)

{

if (head == NULL || head->next == NULL) return head;

ListNode *p = head;

while (p != NULL && p->next != NULL)

if(p->val == p->next->val)

p->next = p->next->next;

else

p = p->next;

return head;

}

};

Java реализация

public class Solution

{

public ListNode deleteDuplicates(ListNode head)

{

if (head == null || head.next == null) return head;

ListNode p = head;

while (p != null && p.next != null)

if(p.val == p.next.val)

p.next = p.next.next;

else

p = p.next;

return head;

}

}