线性表可分为：顺序表与链表。其中，链表可分为单向链表、单向循环链表、双向链表、双向循环链表等。

顺序表与单链表的区别：

1.顺序表可以实现下标的快速访问，单链表则不可以，单链表必须从头依次遍历查找。
2.顺序表在中间或者头部插入节点时必须依次挪动后面节点到下一个节点位置，然而单链表却不用，单链表插入、删除节点比较方便。
3.顺序表每次增容固定大小的空间有可能造成空间浪费，但不用每次插入时都动态开辟空间，单链表每次插入节点时都必须动态开辟空间、删除节点时必须释放掉动态开辟的空间。
4.由于计算机设计的多级缓存机制遵循局部性原理，所以连续访问顺序表时缓存命中率较高，而单链表本身存储比较分散，连续访问时缓存命中率较低还会造成缓存污染。

单链表可分动态链表和静态链表。动态链表是用指针动态地分配存储，静态链表是用数组来模拟的。笔试中多用静态链表(因为new太慢了)，但面试中还是会经常出现动态链表的(leetcode里有很多)。

1.以下为动态单链表的一些操作。

#include<iostream>
#include<cstdio>

using namespace std;

typedef struct node{
    int data;
    struct node *next;
}linknode;

linknode *initiate(linknode *hp){//初始化  
    hp->next=NULL;
    return hp;
} 

bool empty(linknode *hp){//判表空 
    if(hp->next==NULL)  return true;
    return false;
}

int length(linknode *hp){//求表长 
    int n=0;
    hp=hp->next;//定位到第一个元素 
    while(hp->next){
        n++;
        hp=hp->next;
    }
} 

int get(linknode *hp,int i){//取第i个元素 
    int j=1;
    hp=hp->next;
    while(hp && j<i){
        hp=hp->next;
        j++;
    }   
    return hp->data;
} 

linknode *locate(linknode *hp,int e){//定位 
    hp=hp->next;
    while(hp && hp->data!=e)
        hp=hp->next;
    return hp;  
}

bool insertion(linknode *hp,int i,int e){//单链表元素插入 
    int j=0;
    linknode *q;
    while(hp!=NULL && j<i-1){//前驱定位 
        hp=hp->next;
        j++;
    }
    if(hp==NULL || j!=i-1)  return false;
    q=new linknode;
    q->data=e;  q->next=hp->next;
    hp->next=q;
    return true;
}

int main(){
    int n;
    cin>>n;
    int a[11];
    for(int i=1;i<=n;i++)   cin>>a[i];
    linknode *p;
    p=new linknode;
    initiate(p);
    auto o=p;//标记一下位置 
    for(int i=1;i<=n;i++){
        linknode *t;
        t=new linknode;
        t->data=a[i];t->next=p->next;
        p->next=t;
        p=p->next;
    }
    o=o->next;//指向第一个元素 
    for (auto u = o; u; u = u->next)    cout<<u->data<<" ";//输出链表的所有元素 

    return 0;
} 

2.以下为静态链表的操作(acwing 826)

#include <iostream>

using namespace std;

const int N = 100010;


// head 表示头结点的下标
// e[i] 表示节点i的值
// ne[i] 表示节点i的next指针是多少
// idx 存储当前已经用到了哪个点
int head, e[N], ne[N], idx;

// 初始化
void init()
{
    head = -1;
    idx = 0;
}

// 将x插到头结点
void add_to_head(int x)
{
    e[idx] = x, ne[idx] = head, head = idx ++ ;
}

// 将x插到下标是k的点后面
void add(int k, int x)
{
    e[idx] = x, ne[idx] = ne[k], ne[k] = idx ++ ;
}

// 将下标是k的点后面的点删掉
void remove(int k)
{
    ne[k] = ne[ne[k]];
}

int main()
{
    int m;
    cin >> m;

    init();

    while (m -- )
    {
        int k, x;
        char op;

        cin >> op;
        if (op == 'H')
        {
            cin >> x;
            add_to_head(x);
        }
        else if (op == 'D')
        {
            cin >> k;
            if (!k) head = ne[head];
            else remove(k - 1);
        }
        else
        {
            cin >> k >> x;
            add(k - 1, x);
        }
    }

    for (int i = head; i != -1; i = ne[i]) cout << e[i] << ' ';
    cout << endl;

    return 0;
}

反转链表

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

解法一：迭代写法：
定义两个指针： pre 和 cur ；pre 在前 cur 在后。
每次让 pre 的 next 指向 cur ，实现一次局部反转
局部反转完成之后，pre 和 cur 同时往前移动一个位置
循环上述过程，直至 pre 到达链表尾部

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* cur = NULL, *pre = head;
        while (pre != NULL) {
            ListNode* t = pre->next;
            pre->next = cur;
            cur = pre;
            pre = t;
        }
        return cur;
    }
};

解法二：递归写法：
首先我们先考虑 reverseList 函数能做什么，它可以翻转一个链表，并返回新链表的头节点，也就是原链表的尾节点。
所以我们可以先递归处理 reverseList(head->next)，这样我们可以将以head->next为头节点的链表翻转，并得到原链表的尾节点tail，此时head->next是新链表的尾节点，我们令它的next指针指向head，并将head->next指向空即可将整个链表翻转，且新链表的头节点是tail。

空间复杂度分析：总共递归 nn 层，系统栈的空间复杂度是 O(n)O(n)，所以总共需要额外 O(n)O(n) 的空间。
时间复杂度分析：链表中每个节点只被遍历一次，所以时间复杂度是 O(n)O(n)。(转自yxc)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) return head;
        ListNode *tail = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return tail;
    }
};