删除链表中重复的结点_牛客题霸_牛客网【牛客题霸】收集各企业高频校招笔面试题目，配有官方题解，在线进行百度阿里腾讯网易等互联网名企笔试面试模拟考试练习,和牛人一起讨论经典试题,全面提升你的技术能力https://www.nowcoder.com/practice/fc533c45b73a41b0b44ccba763f866ef?tpId=13&tqId=23450&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

【C++解法】

方法一：使用set，暴力解法

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead) {
        if (!pHead) {return pHead;}
        set<int> st;
        ListNode *pre = pHead;
        ListNode *cur = pHead->next;
        while (cur) {
            if (pre->val == cur->val) {
                st.insert(pre->val);
            }
            pre = pre->next;
            cur = cur->next;
        }
        ListNode *vHead = new ListNode(-1);
        pre = vHead;
        cur = pHead;
        while (cur) {
            if (st.count(cur->val)) {
                cur = cur->next;
                pre->next = cur;
            } else {
                pre->next = cur;
                pre = pre->next;
                cur = cur->next;
            }
        }
        pre->next = nullptr;
        return vHead->next;
    }
};

 方法二：遍历直接删除

class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead) {
        ListNode *vHead = new ListNode(-1);
        vHead->next = pHead;
        ListNode *pre = vHead, *cur = pHead;
        while (cur) {
            if (cur->next && cur->val == cur->next->val) {
                cur = cur->next;
                while (cur->next && cur->val == cur->next->val) {
                    cur = cur->next;
                }
                cur = cur->next;
                pre->next = cur;
            } else {
                pre = cur;
                cur = cur->next;
            }
        }
        pre->next = nullptr;
        return vHead->next;
    }
};

方法三：迭代

class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead) {
        ListNode *vHead = new ListNode(-1);
        ListNode *tail = vHead, *cur = pHead;
        while (cur) {
            if (!cur->next || cur->val != cur->next->val) {
                tail->next = cur;
                tail = cur;
            }
            while (cur->next && cur->val == cur->next->val) {cur = cur->next;}
            cur = cur->next;
        }
        tail->next = nullptr;
        return vHead->next;
    }
};

方法四：递归

class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead) {
        if (pHead == nullptr || pHead->next == nullptr) {return pHead;}
        if (pHead->val != pHead->next->val) {
            pHead->next = deleteDuplication(pHead->next);
            return pHead;
        } else {
            ListNode* tmp = pHead->next;
            while (tmp != nullptr && tmp->val == pHead->val) {tmp = tmp->next;}
            return deleteDuplication(tmp);
        }
    }
};