C++如何自定義單向鏈表ListNode

小編給大家分享一下C++如何自定義單向鏈表ListNode，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！

 鏈表有兩種：

•  1、帶頭結(jié)點，頭結(jié)點存放的是鏈表的長度，從第二個節(jié)點開始存放數(shù)據(jù)。

•  2、不帶頭結(jié)點，沒有存放鏈表長度的節(jié)點，從頭結(jié)點開始就存放數(shù)據(jù)。

小編這里定義的鏈表是第二種。

直接上代碼：

#include <iostream>
#include <assert.h>
#include <vector>
#include <algorithm>
using namespace std;

struct ListNode
{
    int val;   //當前節(jié)點的值
    ListNode *next;   //指向下一個節(jié)點的指針
    ListNode() : val(0), next(nullptr) {}   //初始化當前結(jié)點值為默認值0,指針為空
    ListNode(int x) : val(x), next(nullptr) {}    //初始化當前結(jié)點值為x,指針為空
    ListNode(int x, ListNode *next) : val(x), next(next) {}    //初始化當前結(jié)點值為x,下一個績點為next
};


class Solution
{
public:
    //創(chuàng)建長度為len的單向鏈表
    void createList(ListNode *head,int len){
        for(int i=1;i<len;i++)   //len-1個節(jié)點，加上head節(jié)點共len個
        {
            ListNode *node=new ListNode;   //每次都需要實例化一個ListNode
            node->val=i*i;    //為節(jié)點賦值
            node->next=nullptr;
            head->next=node;   //head指向下一個節(jié)點（即當前節(jié)點）
            head=node;     //將當前節(jié)點設(shè)為head
        }
        cout<<"Create a new ListNode with len of "<<len<<" successfully."<<endl;
    }

    //打印鏈表(順序)
    void printList(ListNode *head){
        if(head==nullptr)        
            cout<<"empty list."<<endl;
        else
            while(head!=nullptr)
            {
                cout<<head->val<<'\t';
                head=head->next;
            }
        cout<<endl;
    }

    //打印鏈表（逆序）
    void reversePrintList(ListNode *head){
        //因為ListNode只能根據(jù)next單向索引，無法逆向回溯，所以只能將節(jié)點數(shù)值存在vector中反向輸出。
        //目前只想到了這種方法。
        if(head==nullptr)
        {
            cout<<"empty list."<<endl;
            exit(1);
        }
        else
        {
            vector<int> node;
            while(head!=nullptr)
            {
                node.push_back(head->val);
                head=head->next;
            }
            while(!node.empty())
            {
                //先輸出node中的最后一個元素，再刪除最后一個元素。而不是先對node做reverse再正向輸出。
                cout<<node.back()<<'\t';
                node.pop_back();
            }
            cout<<endl;
        }
    }

    //在鏈表尾節(jié)點添加一個新節(jié)點
    void pushBack(ListNode *head,int val){
        ListNode *node=new ListNode(val,nullptr);   //要添加的新節(jié)點
        if(head==nullptr)
            head=node;
        else
        {
            while(head->next!=nullptr)    //while循環(huán)結(jié)束后head就是尾結(jié)點了
                head=head->next;
            head->next=node;
        }
    }

    //更改鏈表尾節(jié)點數(shù)值
    void changeBackValue(ListNode *head,int val){
        assert(head!=nullptr);
        while(head->next!=nullptr)    //while循環(huán)結(jié)束后head就是尾結(jié)點了
            head=head->next;
        head->val=val;
    }

    //刪除鏈表尾節(jié)點
    void popBack(ListNode *head){
        assert(head!=nullptr);
        while(head->next->next!=nullptr)   //while循環(huán)結(jié)束后head是倒數(shù)第二個節(jié)點，其next指向尾節(jié)點
            head=head->next;
        head->next=nullptr;   //刪除尾節(jié)點
        //注意不要直接delete尾結(jié)點，因為尾結(jié)點的next是nullptr，直接delete nullptr會輸出很多亂碼。
    }

    //刪除鏈表中節(jié)點值等于指定值的節(jié)點（不包括頭節(jié)點）
    void deleteNode(ListNode *head, int val) {
        assert(head != nullptr);
        ListNode *node = head;    //copy一份鏈表
        while (head->next != nullptr)
        {
            if (head->next->val == val)
                node->next=head->next->next;
            head=head->next;
            node=node->next;
        }
    }

    //清空列表
    void clearList(ListNode *head){
        head->next=nullptr;   //清楚頭結(jié)點之后的所有節(jié)點
        //清空列表的功能一直不知道怎么實現(xiàn)，頭結(jié)點不知道怎么刪除。
    }
};


int main()
{
    Solution solution;
    ListNode *listnode=new ListNode(5,nullptr);   //初始化鏈表的head節(jié)點
    solution.printList(listnode);           // 5
    solution.createList(listnode,5);   
    solution.printList(listnode);           // 5       1       4       9       16
    solution.pushBack(listnode,30);
    solution.printList(listnode);           // 5       1       4       9       16      30
    solution.reversePrintList(listnode);    // 30      16      9       4       1       5
    solution.changeBackValue(listnode,88);
    solution.printList(listnode);           // 5       1       4       9       16      88
    solution.popBack(listnode);
    solution.printList(listnode);           // 5       1       4       9       16
    solution.pushBack(listnode,101);
    solution.printList(listnode);           // 5       1       4       9       16      101
    solution.deleteNode(listnode,9);
    solution.printList(listnode);           // 5       1       4       16      101
    solution.clearList(listnode);
    solution.printList(listnode);           // 5
    cout<<"END"<<endl;
    return 0;
}

程序輸出：

5
Create a new ListNode with len of 5 successfully.
5       1       4       9       16
5       1       4       9       16      30
30      16      9       4       1       5
5       1       4       9       16      88
5       1       4       9       16
5       1       4       9       16      101
5       1       4       16      101
5
END

以上是“C++如何自定義單向鏈表ListNode”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對大家有所幫助，如果還想學習更多知識，歡迎關(guān)注億速云行業(yè)資訊頻道！