链表是线性表的链式存储，不需要使用地址连续的存储单元，只通过“链”建立起数据元素之间的逻辑关系。链表的核心操作有插入、删除和查找，其中插入和删除并不需要移动元素，只需要修改指针即可。

链表常见的有：单链表、双向链表、循环链表。

单链表是由Data数据 + Next指针组成的数据结构；第1个内存结构称为链头，最后一个内存结构称为链尾；链尾的Next指针为null；单链表的遍历方向只能从链头到链尾。

双向链表是由Data数据 + Next指针 + Prev指针组成的数据结构；Prev指向的内存结构称为前驱，Next指向的内存结构称为后继；链头的Prev指针为null，链尾的Next指针为null；双向遍历。

循环链表分为单向、双向；单向就是在单链表基础上，把链尾的Next指针指向链头，形成闭环；双向就是在双向链表的基础上，把链尾Next指针指向链头，把链头Prev指针指向链尾，形成闭环。

1. 翻转链表（206）

单链表反转详解（4种算法实现）

迭代思路：

（1）从链表的链头遍历到链尾，逐个改变遍历节点的Next指针，令它指向前一个节点。

（2）定义3个指针left，mid，right，每遍历到一个节点，令mid指向left，然后将三个指针都后移。

（3）直到mid遍历到最后一个节点，执行完操作（2）后，再改变head指向left。

/**
 * prev, cur, next
 */

const reverseList = function(head) {
    let prev = null;
    let cur = head;

    while(cur) {
        // cur.next指的是cur节点的next指针指向，而不是下一个节点
        const next = cur.next;  //保存原本指向的后一个节点，巧妙实现了整体后移
        cur.next = prev; // 令当前节点的next指针指向前一个节点
        prev = cur; // 整体后移
        cur = next; // 整体后移
    }
    return prev;  // 改变head节点的指向
}

时间复杂度：O(n)

空间复杂度：？