算法：从链表中删除重复元素

Question

给出一个链表[未排序]，去除连续重复的元素：

输入：

1 2 3 5 5 6 6 3 2 7

输出：

1 7

第一次迭代后 3 和 3 成为连续重复项，第二次迭代后 2 和 2 成为连续重复项

编程语言不是问题，java/c/c++，什么都行。不推荐使用额外的内存，不需要额外的堆栈或队列，需要在一次迭代中完成。

Answer 1

要一次完成此操作，您需要 doubly linked list，即每个 node 都需要指向 previous 和 下一个 个节点。

使用问题中的例子，当当前节点（用^表示）到达前5个时，

1 2 3 5 5 6 6 3 2 7
      ^

你删除了两个 5，留下 当前节点 指向 3

1 2 3 6 6 3 2 7
    ^

3与下一个节点不匹配，所以在前进到下一个节点后，找到并删除重复的6 , 再次让 当前节点 指向 3

1 2 3 3 2 7
    ^

这次 3 匹配下一个节点，所以 3 被删除，留下 当前节点 指向 2

1 2 2 7
  ^

去掉 2 就大功告成了。总而言之，只要算法删除重复项，当前节点 就会从第一个节点前一个 指针取值 =40=] 已删除。

Answer 2

你可以用 4 个整型变量一次完成，就像 java 中这样：

int current = integers.getFirst();//shows the current number we are reading from the list.
int past = current;               //shows the last number we read.
int iterator = 0;                 //shows where we are.
int NumOfRemoveProcess = 0;       //shows number of nodes we are currently removing.

while (integers.size() > iterator+1){
    iterator++;                      
    current = integers.get(iterator);//getting next value

    if(past == current){             //checking if two(or more consecutive elements are duplicated)
        NumOfRemoveProcess ++;       //shows the number of duplication that we saw.
        integers.remove(iterator);   //remove the new duplicated number.
        iterator --;                 //set iterator after remove.
    }

    else if(NumOfRemoveProcess>0){   //if we removed number in the previous turn.
        iterator--;                  //remove the first duplicated number.
        integers.remove(iterator);
        iterator --;                 //set iterator
        NumOfRemoveProcess = 0;
        past = integers.get(iterator);
    }
    else
        past = current;
}

而整数是整数的链表。 Here 是代码的工作版本。

算法：从链表中删除重复元素

Algorithm : Remove duplicate elements from linked list

algorithm

linked-list