[数据结构与算法]必会算法之链表逆序

先简单说一下链表的特点：

• 链表在空间上不是连续的
• 每存放一个值，都要多开销一个引用空间(即next)
• 每一个节点都认为自己是根节点
• 只要内存足够大，就能存的下，不用担心空间碎片的问题（数组就必须需要一整个连续的空间来存储）

链表逆序
思路：改变next的指向
（1）先定义一个链表：

function Node(value){
    this.value = value;
    this.next = null;
}
let node1 = new Node(1);
let node2 = new Node(2);
let node3 = new Node(3);
let node4 = new Node(4);
let node5 = new Node(5);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
node5.next = null;

（2）链表逆序

function reverseList(node){
    //递归的时候，要先找出递归的出口
    if(node.next.next == null){//倒数第二个节点
        node.next.next = node;
        return node.next;
    }else{
        let result = reverseList(node.next);
        node.next.next = node;
        node.next = null;
        return result;
    }
}

(3)遍历逆序后的链表，输出value

let test = reverseList(node1);
function Test(point){
    if(point == null) return;
    console.log(point.value)
    Test(point.next)
}
let reverse = Test(test);
console.log(reverse)