删除有序链表中的重复元素

题目：

思路：

思路一：由于是有序的链表，所以按一定的顺序，例如从小到大，这样的话，将第一个A节点的值存于一个变量temp之中，设第一个节点为A（head），第二个节点为B（head.next），第三个节点为C（head.next.next），这样如果B的值与A相同，则就是要去掉的，即head.next=head.next.next ，第二节点的位置由第三个的值覆盖。以此类推，便能去重。

思路二：按照第一种方法固然有种简便的方式，但其中也有不少多余的步骤，例如如果ABC三者的值都相同，那么要进行两次赋值操作这明显是多余的，那么我们应该可以尝试遍历到一个不同的，然后直接将重复的一次性清除，减少开销。

思路三：如果这个有序的链表变为了无序的呢，那么明显不能只用一个变量来进行存储，这时候我们可以用set集合来进行处理，这样不管是有序还是无序其实问题都不大，但是对于这种我们又该如何减少开销，再次提高性能。

代码示例：

import java.util.HashSet;

import java.util.Set;

class ListNode {

    int val;

    ListNode next = null;

}

public class Solution {

    public static void main(String[] args) {

        ListNode head = new ListNode();

        head.val = 1;

        ListNode top = head;

        for (int i = 4; i < 6; i++) {

            ListNode temp = new ListNode();

            temp.val = i / 2;

            top.next = temp;

            top = temp;

        }

        ListNode test = head;

        while (head != null) {

            System.out.println(head.val);

            head = head.next;

        }

        System.out.println("end");

        ListNode end = deleteDuplicates2(test);

        while (end != null) {

            System.out.println(end.val);

            end = end.next;

        }

    }

    /**

     * 如果当前为无序链表，这时候可以用一个变量存储一个已经出现过的值，

     * 如果是无序的话这种就不可行了

     *

     * @param head

     * @return

     */

    public static ListNode deleteDuplicates2(ListNode head) {

        if (head == null || head.next == null) //排除传输一个null的链表或者只有一个元素的链表

            return head;

        Set set = new HashSet();        //使用set集合，这样用于判断元素是否已经存在于集合中，且不会存储重复的值

        ListNode next_temp = head;      //头指针

        set.add(next_temp.val);

        while (next_temp != null && next_temp.next != null) {

            if (set.contains(next_temp.next.val)) {

                next_temp.next = next_temp.next.next;

            } else {

                set.add(next_temp.next.val);

                next_temp = next_temp.next;

            }

        }

        return head;

    }

    /**

     * 仅当是当前为有序链表，即按一定的顺序，这时候可以用一个变量存储一个已经出现过的值，

     * 如果是无序的话这种就不可行了

     *

     * @param head

     * @return

     */

    public static ListNode deleteDuplicates1(ListNode head) {

        if (head == null || head.next == null) //排除传输一个null的链表或者只有一个元素的链表

            return head;

        int temp_val = head.val;

        ListNode next_temp = head;      //头指针

        while (next_temp != null && next_temp.next != null) {

            if (next_temp.next.val != temp_val) {

                temp_val = next_temp.next.val;

                next_temp = next_temp.next;

            } else {

                next_temp.next = next_temp.next.next;

            }

        }

        return head;

    }

}