在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表 1->2->3->3->4->4->5 处理后为 1->2->5
数据范围：链表长度满足 0≤n≤1000 ，链表中的值满足 1≤val≤1000
进阶：空间复杂度 O(n)，时间复杂度 O(n)
例如输入{1,2,3,3,4,4,5}时，对应的输出为{1,2,5}，对应的输入输出链表如下图所示：

示例1
输入： {1,2,3,3,4,4,5}
输出： {1,2,5}
示例2
输入： {1,1,1,8}
输出： {8}

解题思路：

主要记住两个关键点：
1、如何去删除重复元素？
2、如何找到新链表的头？

代码实现：

public class Solution_115 {

    private static class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode deleteDuplication(ListNode pHead) {
        if (pHead == null || pHead.next == null) return pHead;

        ListNode dNode = new ListNode(-1);
        ListNode lastNode = dNode;

        while (pHead != null) {
            if (pHead.next != null && pHead.val == pHead.next.val) {
                while (pHead.next != null && pHead.val == pHead.next.val) {
                    pHead = pHead.next;
                }
                pHead = pHead.next;
            } else {
                lastNode.next = pHead;
                lastNode = lastNode.next;

                if (pHead != null)
                    pHead = pHead.next;
            }
        }

        lastNode.next = null;

        return dNode.next;
    }

    public static void main(String[] args) {
        ListNode pHead = new ListNode(1);
        ListNode next_1 = new ListNode(2);
        ListNode next_2 = new ListNode(3);
        ListNode next_3 = new ListNode(3);
        ListNode next_4 = new ListNode(4);
        ListNode next_5 = new ListNode(4);
        ListNode next_6 = new ListNode(5);
        pHead.next = next_1;
        next_1.next = next_2;
        next_2.next = next_3;
        next_3.next = next_4;
        next_4.next = next_5;
        next_5.next = next_6;
        Solution_115 solution_115 = new Solution_115();
        solution_115.deleteDuplication(pHead);
    }
}