剑指offer-删除链表中重复的结点C++实现

剑指offer-删除链表中重复的结点C++实现

剑指offer-删除链表中重复的结点C++实现

原题链接

#include 

using namespace std;

struct ListNode {
    int val;
    struct ListNode *next;

    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode *delete_duplicate(ListNode *head) {
    	// 若链表为空，直接返回头结点
        if (head == nullptr)return head;
        // 创建一个哑结点，哑结点后继指针指向链表头部
        dummy->next = head;
        // cur指针指向哑结点，作为当前结点的前驱结点
        cur = dummy;
        // 开始遍历链表，剔除重复结点
        while (cur->next != nullptr && cur->next->next != nullptr) {
        	// 若当前结点和下一个结点值相等，说明有重复值
            if (cur->next->val == cur->next->next->val) {
            	// 存储重复值用于剔除重复结点
                int x = cur->next->val;
                // 遍历链表，若当前结点值与重复值相等，则断开与当前结点的关联
                while (cur->next != nullptr && cur->next->val == x) {
                    cur->next = cur->next->next;
                }
              // 若当前结点的值与重复值不相等，也就是剔除完当前重复值的所有相关结点后，将当前结点设为新的前驱结点，若链表剩余结点中没有重复值，则当cur指向链表尾部时，结束循环
            } else {
                cur = cur->next;
            }
        }
        // 返回哑结点链接的新链表
        return dummy->next;
    }

private:
    ListNode *cur = nullptr;
    ListNode *dummy = new ListNode(0);
};

思路:
此题的难度不大，但是需要考虑头结点值重复的情况，因此需要创建一个哑结点（伪头结点），之后使用暴力方法，因为链表本身是有序的，所以边遍历边构造链表即可，也就是遍历当前结点，若不重复，则断开它与cur指针的关联。cur指针指向当前结点的前驱结点，若当前结点没有重复值，则cur指针指向当前结点，当前结点作为新的前驱结点。
时间复杂度O(n)，空间复杂度O(1)