Leetcode系列之链表（7）

题目：

给出一个排好序的链表，删除链表中的所有重复出现的元素，只保留原链表中只出现一次的元素。

例如：

给出的链表为1->2->3->3->4->4->5, 返回1->2->5.

给出的链表为1->1->1->2->3, 返回2->3.

思路：

1.思路在于当前的值跟下一个值比较，如果重复，删除下一个，如果不重复，就继续遍历下一个元素

2.要把所有的重复值节点都删完，考虑当前的值即使跟下一个不相等，也有可能与之前重复过的相等

3.使用一个计数器，如果有与当前节点重复的节点，删除掉重复节点之后（因为该链表是有序的，所以重复的就是当前节点的下一个），计数器的值加一。当前节点重复值删除完之后，判断当前节点是否需要删除就是判断计数器的值是否为0，如果不是0则删除该节点。然后继续遍历

4.两种特殊情况，当前节点有重复在链表的头和链表的尾。当为头的时候，因为该链表是不带表头的节点，所以有两种解法，加虚拟表头结点或者分为判断是否为为表头结点，是和不是分为两种情况。对于尾节点来说，因为出循环之后还要判断尾节点是否重复过，如果重复过，删除尾节点。

代码：

/**

* Definition for singly-linked list.

* public class ListNode {

*    int val;

*    ListNode next;

*    ListNode(int x) {

*        val = x;

*        next = null;

*    }

* }

*/

public class Solution {

    public ListNode deleteDuplicates(ListNode head) {

        //添加一个虚拟的表头结点

        ListNode tempHead = new ListNode(0);

        tempHead.next = head;

        //pre之前虚拟头结点，记录元素的前一个位置，如果要删除当前元素，需要前一个位置的指针

        ListNode cur = head, pre = tempHead;

        //计数器的初始值置为0

        int count = 0;

        //当前链表为空或者遍历到链表的最后一个元素时

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

            //如果当前节点和下一个结点相等，删除下一个结点，计数值加1

            if (cur.val == cur.next.val) {

                cur.next = cur.next.next;

                count++;

            } else {

                //不相等的情况下需要判断计数值是否为0来确定是否需要删除当前节点

                if (count > 0) {

                    pre.next = cur.next;

                    count = 0;

                } else {

                    pre = cur;

                }

                cur = cur.next;

            }

        }

        //判断尾节点是否需要删除

        if (count > 0) {

            pre.next = cur.next;

        }

        //返回去除虚拟头结点的链表

        return tempHead.next;

    }

}