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

struct ListNode
{
? ? int val; ? //當(dāng)前節(jié)點(diǎn)的值
? ? ListNode *next; ? //指向下一個(gè)節(jié)點(diǎn)的指針
? ? ListNode() : val(0), next(nullptr) {} ? //初始化當(dāng)前結(jié)點(diǎn)值為默認(rèn)值0,指針為空
? ? ListNode(int x) : val(x), next(nullptr) {} ? ?//初始化當(dāng)前結(jié)點(diǎn)值為x,指針為空
? ? ListNode(int x, ListNode *next) : val(x), next(next) {} ? ?//初始化當(dāng)前結(jié)點(diǎn)值為x,下一個(gè)績(jī)點(diǎn)為next
};


class Solution
{
public:
? ? //創(chuàng)建長(zhǎng)度為len的單向鏈表
? ? void createList(ListNode *head,int len){
? ? ? ? for(int i=1;i<len;i++) ? //len-1個(gè)節(jié)點(diǎn)，加上head節(jié)點(diǎn)共len個(gè)
? ? ? ? {
? ? ? ? ? ? ListNode *node=new ListNode; ? //每次都需要實(shí)例化一個(gè)ListNode
? ? ? ? ? ? node->val=i*i; ? ?//為節(jié)點(diǎn)賦值
? ? ? ? ? ? node->next=nullptr;
? ? ? ? ? ? head->next=node; ? //head指向下一個(gè)節(jié)點(diǎn)（即當(dāng)前節(jié)點(diǎn)）
? ? ? ? ? ? head=node; ? ? //將當(dāng)前節(jié)點(diǎn)設(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){
? ? ? ? //因?yàn)長(zhǎng)istNode只能根據(jù)next單向索引，無法逆向回溯，所以只能將節(jié)點(diǎn)數(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中的最后一個(gè)元素，再刪除最后一個(gè)元素。而不是先對(duì)node做reverse再正向輸出。
? ? ? ? ? ? ? ? cout<<node.back()<<'\t';
? ? ? ? ? ? ? ? node.pop_back();
? ? ? ? ? ? }
? ? ? ? ? ? cout<<endl;
? ? ? ? }
? ? }

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

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

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

? ? //刪除鏈表中節(jié)點(diǎn)值等于指定值的節(jié)點(diǎn)（不包括頭節(jié)點(diǎn)）
? ? 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é)點(diǎn)之后的所有節(jié)點(diǎn)
? ? ? ? //清空列表的功能一直不知道怎么實(shí)現(xiàn)，頭結(jié)點(diǎn)不知道怎么刪除。
? ? }
};


int main()
{
? ? Solution solution;
? ? ListNode *listnode=new ListNode(5,nullptr); ? //初始化鏈表的head節(jié)點(diǎn)
? ? 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;
}