C++单链表
欢迎使用Markdown编辑器
你好！ 这是你第一次使用 Markdown编辑器 所展示的欢迎页。如果你想学习如何使用Markdown编辑器, 可以仔细阅读这篇文章，了解一下Markdown的基本语法知识。
#include 
using namespace std;

template

struct Node

{

T data;

struct Node*next;

};

template 

class LinkList {

private:

Node*front;

public:

LinkList(){front=new Node;front->next=NULL;}

LinkList(T a[],int n);

~LinkList();

void Print();

int GetLength();

Node*Get(int i);

int Locate(T x);

void Insert(int i,T x);

T Delete(int i);

};

template 

LinkList:: LinkList(T a[],int n) {

front=new Node;

Node*r=front;

for(int i=0;i<n;i++)

{

Node*s=new Node;

s->data=a[i];

r->next=s;

r=s;

}

r->next=NULL;

}

/*template 

LinkList::LinkList(T a[],int n)

{

front =new Node;

front->next=NULL;

for(int i=n-1;i>=0;i–)

{

Nodes=new Node;

s->data=a[i];

s->next=front->next;

front->next=s;

}

}/

template 

LinkList::~LinkList() {

Node*p=front;

while§

{

front=p;

p=p->next;

delete front;

}

}

template 

void LinkList:: Print() {      //遍历单链表

Node*p=front;

cout<<“按顺序输出单链表：”<<endl;

if(frontNULL||front->nextNULL)

cout<<“链表为空”<<endl;

while(p->next)

{

p=p->next;

cout<data<<" “;

}

cout<<endl;

}

template 

int LinkList:: GetLength() {

cout<<“链表长度为：”<<endl;

Node*p=front->next;

int j=0;

if(front->nextNULL)return 0;

while§

{

j++;

p=p->next;

}

return j;

}

template 

Node*LinkList:: Get(int i){    //得到第i个元素的地址

Node*p=front->next;

int j=1;

while(p&&j!=i)

{

p=p->next;

j++;

}

return p;

}

template 

int LinkList:: Locate(T x) {

Node*p=front->next;

int j=1;

while§

{

if(p->datax)return j;

p=p->next;

j++;

}

return -1;

}

template 

void LinkList:: Insert(int i,T x) {      //在第i个元素的位置上插入x，原第i个元素移至第（i+1）位置

Node*p=front;

if(i!=1)p=Get(i-1);

if§{

Node*s=new Node;

s->data=x;

s->next=p->next;

p->next=s;

}

else throw"插入错误”;

}

template 

T LinkList:: Delete(int i) {

Node*p=front;

if(i!=1)p=Get(i-1);

Node*q=p->next;

p->next=q->next;

T x=q->data;

delete q;

return x;

}

int main()

{

int a[10];

for(int i=0;i<10;i++)

a[i]=i;

LinkList list(a,10);

list.Print();

cout<<list.GetLength()<<endl;

cout<<list.Get(7)<<endl;

cout<<list.Locate(3)<<endl;

list.Insert(5, 99);

list.Print();

list.Delete(7);

list.Print();

cout<<list.Locate(99)<<endl;

//    list.~LinkList();

}
新的改变
我们对Markdown编辑器进行了一些功能拓展与语法支持，除了标准的Markdown编辑器功能，我们增加了如下几点新功能，帮助你用它写博客：

全新的界面设计 ，将会带来全新的写作体验；
在创作中心设置你喜爱的代码高亮样式，Markdown 将代码片显示选择的高亮样式 进行展示；
增加了 图片拖拽 功能，你可以将本地的图片直接拖拽到编辑区域直接展示；
全新的 KaTeX数学公式 语法；
增加了支持甘特图的mermaid语法 功能；
增加了 多屏幕编辑 Markdown文章功能；
增加了 焦点写作模式、预览模式、简洁写作模式、左右区域同步滚轮设置 等功能，功能按钮位于编辑区域与预览区域中间；
增加了 检查列表 功能。

功能快捷键
撤销：Ctrl/Command + Z

重做：Ctrl/Command + Y

加粗：Ctrl/Command + B

斜体：Ctrl/Command + I

标题：Ctrl/Command + Shift + H

无序列表：Ctrl/Command + Shift + U

有序列表：Ctrl/Command + Shift + O

检查列表：Ctrl/Command + Shift + C

插入代码：Ctrl/Command + Shift + K

插入链接：Ctrl/Command + Shift + L

插入图片：Ctrl/Command + Shift + G
合理的创建标题，有助于目录的生成
直接输入1次#，并按下space后，将生成1级标题。

输入2次#，并按下space后，将生成2级标题。

以此类推，我们支持6级标题。有助于使用TOC语法后生成一个完美的目录。
如何改变文本的样式
强调文本 强调文本
加粗文本 加粗文本
标记文本
删除文本

引用文本

H2O is是液体。
210 运算结果是 1024.
插入链接与图片
链接: link.
图片: 
带尺寸的图片: 
居中的图片: 
居中并且带尺寸的图片: 
当然，我们为了让用户更加便捷，我们增加了图片拖拽功能。
如何插入一段漂亮的代码片
去博客设置页面，选择一款你喜欢的代码片高亮样式，下面展示同样高亮的 代码片.
// An highlighted block
var foo = 'bar';

生成一个适合你的列表

项目

项目

项目






项目1
项目2
项目3


 计划任务
 完成任务

创建一个表格
一个简单的表格是这么创建的：




项目
Value




电脑
$1600


手机
$12


导管
$1


设定内容居中、居左、居右
使用:---------:居中

使用:----------居左

使用----------:居右




第一列
第二列
第三列




第一列文本居中
第二列文本居右
第三列文本居左


SmartyPants
SmartyPants将ASCII标点字符转换为“智能”印刷标点HTML实体。例如：




TYPE
ASCII
HTML




Single backticks
'Isn't this fun?'
‘Isn’t this fun?’


Quotes
"Isn't this fun?"
“Isn’t this fun?”


Dashes
-- is en-dash, --- is em-dash
– is en-dash, — is em-dash


创建一个自定义列表

Markdown
Text-to-HTML conversion tool
Authors
John
Luke

如何创建一个注脚
一个具有注脚的文本。
注释也是必不可少的
Markdown将文本转换为 HTML。
KaTeX数学公式
您可以使用渲染LaTeX数学表达式 KaTeX:
Gamma公式展示 $\Gamma(n) = (n-1)!\quad\forall
n\in\mathbb N$ 是通过欧拉积分
$\Gamma(z) = \int_0^\infty t^{z-1}e^{-t}dt\,.$

你可以找到更多关于的信息 LaTeX 数学表达式here.

新的甘特图功能，丰富你的文章


关于 甘特图 语法，参考 这儿,

UML 图表
可以使用UML图表进行渲染。 Mermaid. 例如下面产生的一个序列图：:

这将产生一个流程图。:


关于 Mermaid 语法，参考 这儿,

FLowchart流程图
我们依旧会支持flowchart的流程图：


关于 Flowchart流程图 语法，参考 这儿.

导出与导入
导出
如果你想尝试使用此编辑器, 你可以在此篇文章任意编辑。当你完成了一篇文章的写作, 在上方工具栏找到 文章导出 ，生成一个.md文件或者.html文件进行本地保存。
导入
如果你想加载一篇你写过的.md文件或者.html文件，在上方工具栏可以选择导入功能进行对应扩展名的文件导入，

继续你的创作。



mermaid语法说明 ↩︎

注脚的解释 ↩︎

[align=center]C++ 单链表[/align]


struct List
{
	int nNumber;
	char cName[10];
	struct List *pNext;
        int nNumberTwo;
};
int size = sizeof(List);


size =24;
                                                      地址
Head                                        0x004850b0
&(Head->nNumber)                  0x004850b0
&(Head->cName[0])                  0x004850b4
&(Head->cName[1])                  0x004850b5
&(Head->cName[9])                  0x004850bd
&(Head->pNext)                       0x004850c0
&(Head->nNumberTwo)            0x004850c4

因为：int 占4个字节
         cName[10]会占用10个字节
         struct List *pNext  是个指针占4个字节
         nNumbeTwo占用4个字节
        那么剩下2个字节分给分配给谁？
关键是这2个字节怎么分配：
      &(Head->cName[9])                  0x004850bd
      &(Head->pNext)                       0x004850c0
      这中间有2个字节间隙，不知分配给了谁？问题就出在这，难道VS不是连续分配地址空间？

很长时间没有接触单链表的算法题，正好借此题回顾一下

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

示例 1:

输入: 1->2->3->4->5->NULL, k = 2

输出: 4->5->1->2->3->NULL

解释:

向右旋转 1 步: 5->1->2->3->4->NULL

向右旋转 2 步: 4->5->1->2->3->NULL
//定义链表
struct ListNode {
    int val;
    ListNode *next;
    //链表初始化，将x赋给val，next附空指针
    ListNode(int x) : val(x), next(NULL) {}
 };
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if(head->next==NULL||k==0){
            return head;
        }
        int n = 1;
        ListNode* temp = head;
        while(temp->next){
            n++;
            temp = temp->next;
        }
        k = k%n;
        if(k==0) return head;
        ListNode* temp1 = head;
        for(int i=1;i<n-k;i++){
            temp1 = temp1->next;
        }
        temp->next = head;
        ListNode* res = temp1->next;
        temp1->next = NULL;
        return res;
    }
};
// find_if找出左空格的边界 注意第三个参数是lambda表达式，返回指针 []内表示lambda的参数，这里为空
void trimLeftTrailingSpaces(string &input) {
    input.erase(input.begin(), find_if(input.begin(), input.end(), [](int ch) {
        return !isspace(ch);
    }));
}
// find_if找出右空格的边界
// 这里find_if 生成的reverse_iterator需要通过base成员函数转化为iterator才能使用，因为存在着偏移量
// https://blog.csdn.net/qq_22194315/article/details/57144854
void trimRightTrailingSpaces(string &input) {
    input.erase(find_if(input.rbegin(), input.rend(), [](int ch) {
        return !isspace(ch);
    }).base(), input.end());
}
// 去除中括号，根据逗号分割
vector<int> stringToIntegerVector(string input) {
    vector<int> output;
    trimLeftTrailingSpaces(input);
    trimRightTrailingSpaces(input);
    input = input.substr(1, input.length() - 2);
    stringstream ss;
    ss.str(input);
    string item;
    char delim = ',';
    while (getline(ss, item, delim)) {
        output.push_back(stoi(item));
    }
    return output;
}
// 字符串转化为链表
ListNode* stringToListNode(string input) {
    // Generate list from the input
    vector<int> list = stringToIntegerVector(input);

    // Now convert that list into linked list
    ListNode* dummyRoot = new ListNode(0);
    ListNode* ptr = dummyRoot;
    for(int item : list) {
        ptr->next = new ListNode(item);
        ptr = ptr->next;
    }
    ptr = dummyRoot->next;
    delete dummyRoot;
    return ptr;
}

int stringToInteger(string input) {
    return stoi(input);
}
// 将链表转化为字符串
string listNodeToString(ListNode* node) {
    if (node == nullptr) {
        return "[]";
    }
    string result;
    while (node) {
        result += to_string(node->val) + ", ";
        node = node->next;
    }
    return "[" + result.substr(0, result.length() - 2) + "]";
}

int main() {
    string line;
    while (getline(cin, line)) {
        ListNode* head = stringToListNode(line);
        getline(cin, line);
        int k = stringToInteger(line);

        ListNode* ret = Solution().rotateRight(head, k);

        string out = listNodeToString(ret);
        cout << out << endl;
    }
    return 0;
}

补充下stringstream的介绍，sstream定义了三个类：istringstream、ostringstream和stringstream分别用来进行流的输入、输出和输入输出操作

由于sstream使用string对象代替字符数组，避免缓冲区溢出的危险；其次，因为传入参数和目标对象的类型会被自动推导出来，所以不存在错误的格式化符的问题。相比c库的数据类型转换，sstream更加安全、自动和直接。

stringstream常见用法介绍
参考

旋转链表

slist.h



#ifndef _SLIST_H_INCLUDED
#define _SLIST_H_INCLUDED

#include <cassert>

template<typename T>
struct Slist_node {
    T element;
    Slist_node* next;
/*把结构体当作一个类，使用构造函数和析构函数初始化*/
    Slist_node() : element(), next(0) {}//可以阻止不应该允许的经过转换构造函数进行的隐式转换的发生
    explicit Slist_node(const T& elem) : element(elem), next(0) {}
    ~Slist_node() { next=0; }
};

template<typename T>
class Slist {

    typedef Slist_node<T>* Ptrn;

public:
    Slist() : hb_head(new Slist_node<T>), hb_size(0) {}
    ~Slist();
    /*一系列对外接口*/
    bool empty() const { return hb_size ? false : true; }
    int size() const { return hb_size; }
    void reverse();
//  void sort() const;
    T value(int pos) const;

    void push_front(const T& elem);
    T pop_front();
    void push_back(const T& elem);
    T pop_back();

    void insert_after(const T& elem, int pos);
    T erase(int pos);
    void erase(int beg, int end);
    void clear();

private:
    Slist_node<T>* hb_head;
    int hb_size;
};

template<typename T>
Slist<T>::~Slist()//析构函数
{
    clear();
    delete hb_head;
}

template<typename T>
void Slist<T>::clear()//删除所有元素。
{
    if (hb_size != 0)
        erase(1,hb_size);
}

template<typename T>
void Slist<T>::erase(int beg, int end)//清除特定范围的函数
{
    if (beg>hb_size || end > hb_size || beg<=0 || end<=0 || beg>end)//判断是否超出范围
        std::cerr<<"error : position out of range!\n";
    else {
        Ptrn ptr=hb_head;
        Ptrn prev=0;
        int i=0;
        while (i != beg) {//从开头查找beg位置且保留beg前的数据
            prev=ptr;
            ptr=ptr->next;
            ++i;
        }
        while (i <= end) {//删除beg~end之间的元素。
            Ptrn ptm=ptr;
            ptr=ptr->next;
            delete ptm;
            --hb_size;
            ++i;
        }
        prev->next=ptr;//两边要对接起来
    }
}

template<typename T>
T Slist<T>::erase(int pos)//删除特定位置的某个元素
{
    assert(pos<=hb_size && pos!=0);
    /*现计算括号内条件 ，如果其值为假（即为0），那
    么它先向stderr打印一条出错信息，然后通过调用 abort 来终止程序运行*/
    Ptrn ptr=hb_head;
    Ptrn prev=0;
    int i=0;
    while (i != pos) {//从头开始找到位置且保留前面的数据。
        prev=ptr;
        ptr=ptr->next;
        ++i;
    }
    T t=ptr->element;//复制要删除的元素的值
    prev->next=ptr->next;
    delete ptr;
    --hb_size;
    return t;
}

template<typename T>
void Slist<T>::insert_after(const T& elem, int pos)//在pos位置后插入elem
{
    Ptrn ptr=hb_head;
    int i=0;
    while ( i!= pos) {
        ptr=ptr->next;
        ++i;
    }

    Slist_node<T>* pSln=new Slist_node<T>;
    pSln->element=elem;
    pSln->next=ptr->next;
    ptr->next=pSln;
    ++hb_size;
}

template<typename T>
void Slist<T>::push_front(const T& elem)//插入到首部
{
    insert_after(elem,0);
}

template<typename T>
void Slist<T>::push_back(const T& elem)//插入到最后。
{
    insert_after(elem,hb_size);
}

template<typename T>
T Slist<T>::pop_front()//删除第一位元素
{
    return erase(1);
}

template<typename T>
T Slist<T>::pop_back()//删除最后一位元素
{
    return erase(hb_size);
}

template<typename T>
inline T Slist<T>::value(int pos) const//查看当前位置pos对应的值。
{
    Ptrn ptr=hb_head;
    int i=0;
    while (i != pos) {
        ptr=ptr->next;
        ++i;
    }
    return ptr->element;
}

template<typename T>
void Slist<T>::reverse()//单链表反转。
{
    Ptrn pbeg=hb_head->next;//备份原链表头节点
    hb_head->next=0;        //设置当前头节点
    hb_size=0;
    Ptrn ptr=pbeg;          //原地址赋给ptr
    while (ptr != 0) {
        push_front(ptr->element);//将后面的元素依次插入到首部。
        Ptrn ptm=ptr;           //删除当前位置的刚插入的元素。
        ptr=ptr->next;
        delete ptm;
    }
}

#endif

test.cpp



#include <iostream>
#include "slist.h"

int main()
{
    Slist<int> slist;
    int i=slist.size();
    std::cout<<i<<std::endl;

    slist.push_back(2);
    for (int j1=0; j1<slist.size(); ++j1)
        std::cout<<slist.value(j1+1)<<'-';
    std::cout<<std::endl;
    slist.push_front(4);
    for (int j2=0; j2<slist.size(); ++j2)
        std::cout<<slist.value(j2+1)<<'-';
    std::cout<<std::endl;
    slist.insert_after(7,1);
    i=slist.size();
    std::cout<<i<<std::endl;
    for (int j3=0; j3<slist.size(); ++j3)
        std::cout<<slist.value(j3+1)<<'-';
    std::cout<<std::endl;

    slist.reverse();
    std::cout<<slist.size()<<std::endl;
    for (int j4=0; j4<slist.size(); ++j4)
        std::cout<<slist.value(j4+1)<<'-';
    std::cout<<std::endl;
    slist.clear();
    std::cout<<slist.size()<<std::endl;
    return 0;
}