题目描述

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。

样例

输入: 1->2->3->3->4->4->5
输出: 1->2->5

输入: 1->1->1->2->3
输出: 2->3

算法分析

设置虚拟头结点dummy，p指针指向的是上一个没有重复的元素的位置，初始位置是dummy，q从p.next开始，一直走到第一个与q.next不同元素的位置，即整个绿色的点都是相同的点，最终q走到如图所示的位置

• 若p.next.next = q，表示绿色区域的点只有一个，不重复，p = p.next
• 若p.next.next != q，表示绿色区域的点不止一个，重复，p.next = q

时间复杂度 $O(n)$

Java 代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        ListNode p = dummy;
        while(p.next != null)
        {
            ListNode q = p.next;
            while(q != null && q.val == p.next.val)
                q = q.next;
            if(p.next.next == q) p = p.next;//没有重复
            else p.next = q;//表示重复

        }
        return dummy.next;
    }
}