题解 | #删除链表中重复的结点#

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
  public:
    ListNode* deleteDuplication(ListNode* pHead) {
        // 原链表为空
        if (pHead == nullptr) {
            return pHead;
        }
        ListNode* p = pHead;
        vector<int> v;
        // 将链表中重复的结点数值存储到数组中
        while (p->next != nullptr) {
            if (p->val == p->next->val) {
                if (v.size() == 0) {
                    v.push_back(p->val);
                } else if (p->val != v.back()) {
                    v.push_back(p->val);
                }
            }
            p = p->next;
        }
        // 从头开始遍历链表
        p = pHead;
        int index = 0;
        while (p->next != nullptr) {
            // 链表中没有重复的数值
            if (v.size() == 0) {
                return pHead;
            }
            // 当前结点的下一个结点是待删除的重复结点
            if (p->next->val == v[index]) {
                // 下一个结点与当前结点值相同，即要将头指针也向后移
                if (p == pHead && p->val == p->next->val) {
                    while (p->next->val == v[index]) {
                        pHead = pHead->next;
                        p = pHead;
                        if (p->next == nullptr) {
                            pHead = nullptr;
                            return pHead;
                        }
                    }
                    pHead = pHead->next;
                    p->next = nullptr;
                    p = pHead;
                    //对应数值的结点删除完毕，准备删除下一个数值的结点
                    ++index;
                } else {  // 正常删除下一个结点
                    ListNode* q = p->next;
                    p->next = q->next;
                    q->next = nullptr;
                    delete q;
                    // 已经删除到最后一个结点，跳出循环避免越界访问
                    if (p->next == nullptr) {
                        break;
                    }
                    // 下一个结点不用再删除，可以准备删除下一个数值的结点
                    if (p->next->val != v[index]) {
                        ++index;
                    }
                    // 一次删除完毕后从当前结点开始继续循环，以确定下一个结点是否也需要删除
                    continue;
                }
            } else {  // 不需要执行删除，指针正常后移寻找
                p = p->next;
            }
        }
        return pHead;
    }
};