时间戳

首页 > 解决方案 > 在链表类中实现 removeDuplicates() 方法

c++ - 在链表类中实现 removeDuplicates() 方法

问题描述

#ifndef INT_LINKED_LIST
    #define INT_LINKED_LIST
    using namespace std;
    class IntSLLNode {
    public:
        IntSLLNode() {
        next = 0;
        }
        IntSLLNode(int el, IntSLLNode *ptr = 0) {
        info = el; next = ptr;
        }
        int getInfo() const
        {
            return this->info;
        }
        IntSLLNode getNext() const
        {
            return this->next;
        }
    private:
        int info;
        IntSLLNode *next;
    };
    
    class IntSLList {
    public:
        IntSLList() {
            head = tail = 0;
        }
        ~IntSLList();
        int isEmpty() {
            return head == 0;
        }
        void addToHead(int);
        void addToTail(int);
        int deleteFromHead(); // delete the head and return its info;
        int deleteFromTail(); // delete the tail and return its info;
        void deleteNode(int);
        bool isInList(int) const;
        void removeDuplicates();
    private:
        IntSLLNode *head, *tail;
    };
    #endif

标签： c++oop

解决方案

简单的方法：删除除第一个元素之外的所有第一个元素，删除除第一个元素之外的所有第二个元素，……依此类推，直到您传递了最后一个元素。

假设你有

IntSLLNode* deduplicate(IntSLLNode* start)

start->info从其后续节点中删除所有重复项并返回可能更新的尾指针，您可以编写

void removeDuplicates()
{
    IntSLLNode* current = head;
    while (current)
    {
        tail = deduplicate(current);
        current = current->next;
    }
}

实施deduplicate左侧作为练习。

推荐阅读