方法一：遍历

先遍历到尾部
在遍历过程中让节点新增属性 pre 使单向链表变成双向链表
遍历到尾部时开始指向反转并删除节点的 pre 属性

边界条件：

在头部时，节点的 pre 属性为 null
到尾部时，节点的 next 属性为 null

function reverseList(head) {
    // 链表只有一个元素时
    if( head.next === null ) return head;
    // 否则
    let current = head.next,
        preNode = head;
    // 链表反向后原来的头就变成尾了
    preNode.pre = null; // 相当于 head.pre = null;
    while( current.next ){
        current.pre = preNode;  // 建立反向联系
        // 指针后移
        preNode = current;
        current = current.next;
    }
    current.pre = preNode;  // 建立最后一个元素和倒数第二个元素的联系

    // 至此，一个双向链表已经完成了
    // 然后就要开始往前遍历了
    while( current.pre ){
        // 指向反向
        current.next = current.pre;
        // 使"先指针"和"后指针"都指向当前对象
        preNode = current;
        // "先指针"前移
        current = current.pre;
        // 将初始从前向后遍历时新增的属性删掉
        delete preNode.pre;
    }
    // 修正原链表第一个元素的指向
    current.next = current.pre;
    delete current.pre;
}

方法二：递归

每次只对一个元素进行操作，如果当前元素的后一项不为空，则递归调用本函数，传入的值为当前元素的后一项
在每次递归形成的作用域中使后面的元素指向当前元素，当前元素指向空

边界条件：

当传入参数的属性 next 为 null时，说明这个元素是链表的最后一个元素

function reverseList(node) {  // 传入链表的头结点
    if( node.next === null ) {
        /*
        * 能走到这里的有只有两种情况：
        *   1.链表只有一个元素
        *   2.链表不止一个元素同时已经遍历到链表的最后一个元素了
        * */
        return node;
    } else{
        const nextNode = reverseList(node.next);
        nextNode.next = node;
        node.next = null;   // 如果不是原链表的第一个元素，则会在上一次递归的作用域中被修改
        return node;
    }
}

测试代码：

function CreateNode(val){
    this.val = val;
    this.next = null;
}

function CreateList(...nodes){
    this.head = nodes[0];
    this.length = nodes.length;
    for( var i = 0; i < nodes.length - 1; i++ ){
        if( nodes[i+1] ){
            nodes[i].next = nodes[i+1];
        }
    }
}

function reverseList(head){
    // 选择上面所示的任意一个翻转链表的函数
}

const node1 = new CreateNode(1);
const node2 = new CreateNode(2);
const node3 = new CreateNode(3);
const node4 = new CreateNode(4);
const node5 = new CreateNode(5);
const list = new CreateList(node1, node2, node3, node4, node5);
console.log(node1);
reverseList(node1);
console.log(node5);

leetcode206：反转链表 #14

Description

Activity

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions