解法一：虚拟结点

此题要求删除「所有的」重复结点，而存在「原链表头结点出现重复」这种情况。因此，为了实现方便，定义虚拟结点dummy，其next指针指向原头结点。

思路如图所示。

1. 定义指针p，用以遍历链表；定义指针tail，用以指向当前「无重复链表」表尾；
2. 每次p指针向前移动，并比较「当前位置取值」与「下一结点取值」是否相等：
   1. 若不相等，说明当前位置为非重复结点，更新tail指针；
   2. 否则，p指针不断向前移动直至「当前结点与下一结点取值不同为止」；
   3. 当p到达链表表尾而最外层while循环仍未结束，说明「链表表尾为非重复结点」，更新tail指针。

注意：在最外层while循环结束时，需要重置tail指针的next指针为空，否则无法完成「删除」这一操作。

代码实现：

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead) {
        if (!pHead) 
            return NULL;
        ListNode* dummy = new ListNode(-1); // 定义虚拟结点
        dummy->next = pHead; 
        ListNode* p = new ListNode(-1), *tail = new ListNode(-1); // p指针用来遍历链表，tail指针用来表示当前链表表尾
        p = pHead; 
        tail = dummy; 
        while (p) {
            if ((p->next && p->val != p->next->val) || !p->next) { // 如果无重复结点，或者达到了链表表尾
                // 更新tail指针
                tail->next = p; 
                tail = tail->next;
            }
            while (p->next && p->val == p->next->val) { // 有重复
                p = p->next; 
            }
            p = p->next; 
        }
        tail->next = NULL; // 重置tail指针next指针为空
        return dummy->next; 
    }
};

该方法需要遍历整个链表，时间复杂度为O(N)；

该方法未使用额外空间（除部分指针外），空间复杂度为O(1)。

解法二：快慢指针

解法二的思路与解法一类似，思路如图所示：

1. 定义两个指针（slow、fast），以及虚拟结点dummy，初始化三者指针，slow和fast相邻；
2. 当遇到重复时，「只有fast指针」向前移动，此时slow和fast不相邻；
3. 若没有重复，则slow指针和fast指针都向前移动一步；

「因此，当出现重复时，slow指针和fast指针必不相邻，此时更新二者的位置可以实现删除的效果。」

据上述思路，实现的代码如下：

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead) {
        if (!pHead)
            return NULL;
        ListNode* slow = new ListNode(-1), *fast = new ListNode(-1), *dummy = new ListNode(-1); 
        dummy->next = pHead; 
        // 初始化两个指针
        slow = dummy; 
        fast = dummy->next; 
        while (fast) {
            // 遇到重复
            while (fast->next && fast->val == fast->next->val) {
                fast = fast->next; 
            }
            // 遇到重复
            if (slow->next != fast) {
                slow->next = fast->next; 
                fast = slow->next; 
            } else { // 没有重复
                fast = fast->next; 
                slow = slow->next; 
            }
        }
        return dummy->next;
    }
};

该方法需要遍历整个链表，时间复杂度为O(N)；

该方法未使用额外空间（除部分指针外），空间复杂度为O(1)。