1.上篇单链表相关知识续

        对于上篇中剩下的单链表的知识还有如下。

判断链表是否存在环及环的入口节点：

// 判断链表是否存在环，环的入口节点是什么
bool IsListCircle(Node *head, int &val)
{
    Node *fast = head;
    Node *slow = head;
    while (fast != nullptr && fast->next_ != nullptr) // 循环判断继续的条件
    {
        fast = fast->next_->next_;
        slow = slow->next_;
        if (fast == slow) // 相遇，存在环
        {
            fast = head;
            while (fast != slow)
            {
                fast = fast->next_;
                slow = slow->next_;
            }
            val = fast->data_;
            return true;
        }
    }
    return false;
}

注意：1.要注意其中循环继续的条件，因为对于fast指针要当前节点的下下个节点，避免出现空指针访问的错误。

判断两个链表是否相交及交点节点：

bool IsListIntersect(Node *head1, Node *head2, int &val)
{
    Node *p = head1->next_;
    Node *q = head2->next_;
    int cnt1 = 0, cnt2 = 0;
    while (p != nullptr)
    {
        cnt1++;
        p = p->next_;
    }
    while (q != nullptr)
    {
        cnt2++;
        q = q->next_;
    }
    p = head1;
    q = head2;
    if (cnt1 > cnt2)
    {
        for (int i = cnt1 - cnt2; i > 0; i--)
        {
            p = p->next_;
        }
    }
    else
    {
        for (int i = cnt2 - cnt1; i > 0; i--)
        {
            q = q->next_;
        }
    }
    while (p != nullptr)
    {
        if (p == q)
        {
            val = p->data_;
            return true;
        }
        p = p->next_;
        q = q->next_;
    }
    return false;
}

删除不带头节点的倒数第k个节点：

Node *DeleteNode(Node *h, int pos)
{
    if (h == nullptr || pos <= 0)
        return h;
    Node head;
    head.next_ = h;
    Node *p = &head;
    Node *q = &head;
    for (int i = 0; i < pos; i++)
    {
        if (q != nullptr)
        {
            q = q->next_;
        }
        else
        {
            return h;
        }
    }
    while (q->next_ != nullptr)
    {
        q = q->next_;
        p = p->next_;
    }
    q = p->next_;
    p->next_ = q->next_;
    return head.next_;
}

该知识点与找到链表中倒数第k个节点非常相似，对于没有头节点的链表如果有头节点更好解决我们可以实现一个头节点。

Node *MoveList(Node *head, int num)
{
    if (head == nullptr || num <= 0)
    {
        return head;
    }
    Node *p = head;
    int count = 0;
    while (p->next_ != nullptr)
    {
        count++;
        p = p->next_;
    }
    count = count + 1;
    p->next_ = head;
    for (int i = count - (num % count); i > 0; i--)
    {
        head = head->next_;
        p = p->next_;
    }
    p->next_ = nullptr;
    return head;
}

对于链表的移动我们可以采用先连接成圆再解除圆来解决。

2.单向循环链表的c++实现及相关知识

(1)c++实现

class SCList
{
public:
    SCList()
    {
        head_ = new Node();
        tail_ = head_;
        head_->next_ = head_; // 当只有一个头节点时要让头节点的地址域保存头节点的地址
    }
    ~SCList()
    {
        Node *p = head_->next_;
        while (p != head_)
        {
            head_->next_ = p->next_;
            delete p;
            p = head_->next_;
        }
        delete head_;
    }
    // 头插法
    void InsertHead(int val)
    {
        Node *node = new Node(val);
        node->next_ = head_->next_;
        head_->next_ = node;
        if (node->next_ == head_)
        {
            tail_ = node;
        }
    }
    // 尾插法
    void InsertTail(int val)
    {
        Node *node = new Node(val);
        node->next_ = head_; // 因为是循环链表所以要注意，在尾插法时new出的节点的next保存头节点的地址
        tail_->next_ = node;
        tail_ = node;
    }
    // 删除指定元素
    void Remove(int val)
    {
        Node *p = head_->next_;
        Node *q = head_;
        while (p != head_)
        {
            if (p->data_ == val)
            {
                q->next_ = p->next_;
                delete p;
                if (q->next_ == head_)
                {
                    tail_ = q;
                }
                return;
            }
            else
            {
                q = p;
                p = p->next_;
            }
        }
    }
    // 查找指定元素
    bool Find(int val)
    {
        Node *p = head_->next_;
        while (p != head_)
        {
            if (p->data_ == val)
            {
                return true;
            }
            p = p->next_;
        }
        return false;
    }
    // 显示链表
    void show()
    {
        Node *p = head_->next_;
        while (p != head_)
        {
            cout << p->data_ << " ";
            p = p->next_;
        }
        cout << endl;
    }

private:
    struct Node
    {
        Node(int data = 0) : data_(data), next_(nullptr) {}
        int data_;
        Node *next_;
    };
    Node *head_;
    Node *tail_;
};

注意：1.在循环链表中当只有一个头节点时，头节点的地址域要指向头节点地址。2.在循环链表进行尾插法时要将尾节点的地址域指向头节点。

(2)相关知识

特点：末尾节点的地址域指向了头节点。

约瑟夫环问题：

void Joseph(Node *head, int k, int m)
{
    Node *p = head;
    Node *q = head;
    while (q->next_ != head)
    {
        q = q->next_;
    }
    for (int i = 1; i < k; i++)
    {
        q = p;
        p = p->next_;
    }
    while (1)
    {
        if(q == p)
        {
            cout << p->data_ << " ";
            delete p;
            return;
        }
        for (int i = 1; i < m; i++)
        {
            q = p;
            p = p->next_;
        }
        cout << p->data_ << " ";
        q->next_ = p->next_;
        delete p;
        p = q->next_;
    }
}

3.双向链表的c++实现及相关知识

(1)c++实现

struct Node
{
    Node(int data = 0)
        :data_(data)
        ,pre_(nullptr)
        ,next_(nullptr)
    {}
    int data_;
    Node *pre_;
    Node *next_;
};


class DoubleList
{
public:
    DoubleList()
    {
        head_ = new Node();
    }
    ~DoubleList()
    {
        Node *p = head_;
        while(p != nullptr)
        {
            head_ = head_->next_;
            delete p;
            p = head_;
        }
    }
    //头插法
    void InsertHead(int val)
    {
        Node *node = new Node(val);
        node->next_ = head_->next_;
        node->pre_ = head_;
        if(head_->next_ != nullptr)
        {
            head_->next_->pre_ = node;
        }
        head_->next_ = node;
    }
    //尾插法
    void InsertTail(int val)
    {
        Node *node = new Node(val);
        Node *p = head_;
        while(p->next_ != nullptr)
        {
            p = p->next_;
        }
        p->next_ = node;
        node->pre_ = p;
    }
    //删除指定的元素的第一个元素
    void Remove(int val)
    {
        Node *p = head_->next_;
        while(p != nullptr)
        {
            if(p->data_ == val)
            {
                p->pre_->next_ = p->next_;
                if(p->next_ != nullptr)
                {
                    p->next_->pre_ = p->pre_; //当要删除的节点时尾节点时，不需要进行尾节点后面节点的访问了
                }
                delete p;
                return;
            }
            else
            {
                p = p->next_;
            }
        }
    }
    //查找
    bool Find(int val)
    {
        Node *p = head_->next_;
        while(p != nullptr)
        {
            if(p->data_ == val)
            {
                return true;
            }
            p = p->next_;
        }
        return false;
    }
    //显示
    void Show()
    {
        Node *p = head_->next_;
        while(p != nullptr)
        {
            cout << p->data_ << " ";
            p = p->next_;
        }
        cout << endl;
    }
private:
    Node *head_;
};

1.当在双向链表进行尾节点的删除时不需要再对其后面的节点进行访问，所以要加上判断处理。

(2)相关知识

特点：头节点的pre是nullptr，尾节点的next是nullptr。

4.双向循环链表的c++实现及相关知识

(1)c++实现

struct Node
{
    Node(int data = 0)
        : data_(data), pre_(nullptr), next_(nullptr)
    {
    }
    int data_;
    Node *pre_;
    Node *next_;
};

class DCList
{
public:
    DCList()
    {
        head_ = new Node();
        head_->next_ = head_;
        head_->pre_ = head_;
    }
    ~DCList()
    {
        Node *p = head_->next_;
        while (p != head_)
        {
            head_->next_ = p->next_;
            p->next_->pre_ = head_;
            delete p;
            p = head_->next_;
        }
    }
    // 头插法
    void InsertHead(int val)
    {
        Node *node = new Node(val);
        node->next_ = head_->next_;
        node->pre_ = head_;
        head_->next_->pre_ = node;
        head_->next_ = node;
    }
    // 尾插法
    void InsertTail(int val)
    {
        Node *node = new Node(val);
        Node *p = head_->pre_;
        p->next_ = node;
        node->pre_ = p;
        node->next_ = head_;
        head_->pre_ = node;
    }
    // 删除指定的元素的第一个元素
    void Remove(int val)
    {
        Node *p = head_->next_;
        while (p != head_)
        {
            if (p->data_ == val)
            {
                p->pre_->next_ = p->next_;
                p->next_->pre_ = p->pre_; 
                delete p;
                return;
            }
            else
            {
                p = p->next_;
            }
        }
    }
    // 查找
    bool Find(int val)
    {
        Node *p = head_->next_;
        while (p != head_)
        {
            if (p->data_ == val)
            {
                return true;
            }
            p = p->next_;
        }
        return false;
    }
    // 显示
    void Show()
    {
        Node *p = head_->next_;
        while (p != head_)
        {
            cout << p->data_ << " ";
            p = p->next_;
        }
        cout << endl;
    }

private:
    Node *head_;
};

(2)相关知识

特点：头节点的pre指向尾节点，尾节点的next指向头节点。

5.顺序栈的c++实现及相关知识

(1)c++实现

class SeqStack
{
public:
    SeqStack(int size = 10)
        : cap_(size), top_(0)
    {
        pstack_ = new int[size];
    }
    ~SeqStack()
    {
        delete pstack_;
        cap_ = 0;
        top_ = 0;
        pstack_ = nullptr;
    }
    // 入栈
    void push(int val)
    {
        if (cap_ == top_)
        {
            expand(2 * cap_);
        }
        pstack_[top_] = val;
        top_++;
    }
    // 出栈
    void pop()
    {
        if (top_ == 0)
        {
            throw "stack is empty!";
        }
        top_--;
    }
    // 访问栈顶元素
    int top()
    {
        if (top_ == 0)
        {
            throw "stack is empty!";
        }
        return pstack_[top_ - 1];
    }
    // 判断是否为空
    bool empty()
    {
        if (top_ == 0)
        {
            return true;
        }
        return false;
    }
    // 获取栈的有效元素个数
    int size()
    {
        return top_;
    }

private:
    int *pstack_;
    int top_;
    int cap_;

    void expand(int size)
    {
        int *p = new int[size];
        memcpy(p, pstack_, top_ * sizeof(int));
        delete[] pstack_;
        pstack_ = p;
        cap_ = size;
    }
};

(2)相关知识

特点：底层依赖数组实现

6.链式栈的c++实现及相关知识

(1)c++实现

class LinkStack
{
public:
    LinkStack()
    {
        head_ = new Node();
    }
    ~LinkStack()
    {
        Node *p = head_;
        while (p != nullptr)
        {
            head_ = head_->next_;
            delete p;
            p = head_;
        }
    }
    // 入栈
    void push(int val)
    {
        Node *node = new Node(val);
        node->next_ = head_->next_;
        head_->next_ = node;
        size_++;
    }
    // 出栈
    void pop()
    {
        if (head_->next_ == nullptr)
        {
            throw "stack is empty!";
        }
        Node *p = head_->next_;
        head_->next_ = p->next_;
        delete p;
        size_--;
    }
    // 获取栈顶元素
    int top()
    {
        if (head_->next_ == nullptr)
        {
            throw "stack is empty!";
        }
        return head_->next_->data_;
    }
    // 判空
    bool empty()
    {
        return head_->next_ == nullptr;
    }
    // 获取栈有效元素个数
    int size()
    {
        return size_;
    }

private:
    struct Node
    {
        Node(int data = 0)
            : data_(data), next_(nullptr)
        {
        }
        int data_;
        Node *next_;
    };
    Node *head_;
    int size_;
};

(2)相关知识

特点：底层依赖链表实现。