思路一：
遍历链表，把遍历的值存储到一个Hashtable中，在遍历过程中，若当前访问的值在Hashtable中已经存在，则说明这个数据是重复的，因此就可以删除。
优点：时间复杂度较低O(n)
缺点：在遍历过程中需要额外的存储空间来保存已遍历过的值
思路二：
对链表进行双重循环遍历，外循环正常遍历链表，假设外循环当前遍历的结点为cur，内循环从cur开始遍历，若碰到与cur所指向结点值相同，则删除这个重复结点
优点：不需要额外的存储空间
缺点：时间复杂度较高O(n^2)
思路三：
外循环当前遍历的结点为cur，内循环从链表头开始遍历至cur，只要碰到与cur值相同的结点就删除该结点，同时内循环结束，因为与cur相同的结点只可能存在一个（如果存在多个，在前面的遍历过程中已经被删除了）
优点：采用这种方法在特定的数据发布的情况下会提高算法的时间复杂度
import java.util.*; /** * @author * @date * @function 从链表中删除重复元素 */ public class deleteDuplecate { //法一：优点是时间复杂度低，但是需要额外的存储空间来保存遍历过的值。时间复杂度O(n) public void delete_v1(Node head){ Hashtable<Integer,Integer> table=new Hashtable<Integer,Integer>(); Node temp=head; Node pre=null; //辅助链表的头节点 while(temp!=null){ if(table.containsKey(temp.data)) pre.next=temp.next; else{ table.put(temp.data, 1); pre=temp; } temp=temp.next; } } //法二：双重循环遍历链表,优点：不需要额外的存储空间.时间复杂度O(n^2) public void delete_v2(Node head){ Node p=head; while(p!=null){ Node q=p; while(q.next!=null){ if(q.next.data==p.data){ q.next=q.next.next; }else q=q.next; } p=p.next; } } //法三：外循环当前遍历的结点为p，内循环从表头开始遍历至p public void delete_v3(Node head){ Node p=head; while(p!=null){ Node q=head; while(q.next!=p && q.next!=null){ if(q.next.data==p.data){ q.next=q.next.next; }else q=q.next; } p=p.next; } } } class Node{ Node next=null; int data; public Node(int data){ this.data=data; } }