借鉴循环链表思想

观察input与output结点之间的差别，6->2 变为了 2->6 所以我们可在遍历链表时记录下每个结点的新next结点
即现有链表上的上一个结点

此时，我们可以看到，如果只看prev结点属性，从链表尾向表头看（从右向左），此时链表已经实现反转的效果了
我们接下来要做的，只需要把prev属性替换为next属性即可[滑稽.png]

此时head指针指向链表末尾，然后在链表末尾往回遍历的过程中，实现“属性替换”

head.next = head.prev;
head = head.prev;
为了链表整洁，删除新增的prev属性

function reverseList(head) {
    if(head==null||head.next ==null){
        return head;
    }
    // 遍历1
    let prev = null; // 初始化 head 结点的prev为null
    while(head) {
        head.prev = prev;
        prev = head;
        head = head.next;
    }
    // 此时head指向null 指向链尾的是prev
    head = prev;
    let p = head;
    let pprev = p.prev;
    // 遍历2 将prev指向的值替换到next
    while (p && pprev) { // 因为这里要引用p.prev 而 while里又要删去prev属性 所以使用pprev变量
        delete p.prev;
        p.next = pprev;
        p = pprev;
        pprev = p.prev;
    } 
    // 头结点处理
    p.next = null;
    delete p.prev;
    return head;
}

优化-顺向遍历时修改指向

第一种方法是给链表上的每个结点都加上了prev属性，实现了链表结点直接的链接反转，其实仔细回顾实现方式，关键的步骤：
1、两个指针同时指向prev结点和当前结点
2、当前结点.next = prev结点
3、更新prev结点、当前结点
4、遍历结束，返回链尾作为新表头

所以，可以将两边遍历优化为一遍，且无需全局的prev属性记录上一个结点
只需在第一次遍历的时候，修改指向即可，

当前结点.next = prev结点 & prev结点.next 不再指向当前结点（由于prev的next在上一轮的当前结点.next即修改了指向所以无需再修改）

// 优化，依赖局部变量修改链表里结点的指向关系
function reverseList(head) {
    if(head==null||head.next ==null){
        return head;
    }
    let prev = null;
    while (head && head.next) {
        let next_temp = head.next;
        head.next = prev;
        prev = head;
        head = next_temp;        
    }
    head.next = prev;
    return head;
}

优化-链尾开始修改指向

我们除了在第一次遍历的时候修改每两个结点之间的指向，遍历到结束的时候直接返回链尾作为新表头外，可以在遍历到链尾的时候再开始修改结点之间的关联
假设现在已经到链尾了 head.next = null

通过反向遍历修改结点指向，必须手动断开两个结点直接链接（head.next = null ）
而最简便的方式能一次触达链尾且顺其自然地反向遍历的实现，即是递归啦~
递归出口即是链尾处，递归弹栈时即为反向遍历过程

function reverseList2(head){
    // 链尾
    if(head==null||head.next ==null){
        return head;
    }
    // 返回新链表的头节点 即原链尾
    let newhead = reverseList(head.next);
    // 此时的head是倒数第二个节点 (当第一次回溯的时候)
    head.next.next = head;
    head.next = null;// 断开原链接 不然要环
    return newhead;
}

借鉴链表头插法

使用头插法建立链表时，链表与输入顺序相反，利用此特性，我们可以在遍历链表时，使用头插法将当前遍历元素塞入新head的后面，然后返回新head即可

// 头插法思路借鉴
function reverseList1(head) {
    let dummy = new ListNode();
    let curr = dummy;
    while(head){
        let temp = head.next;
        head.next = curr.next;
        curr.next = head;
        head = temp;
    }
    return dummy.next ;
};

🤔数据结构与算法

反转链表

借鉴循环链表思想

优化-顺向遍历时修改指向

优化-链尾开始修改指向

借鉴链表头插法

扩展