1. 先上代码:先准备好一个 1 2 3  的链表 temp

function ListNode(val, next) {
    this.val = (val===undefined ? 0 : val)
    this.next = (next===undefined ? null : next)
}

let temp = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode)));

2. 铺垫一下知识,请看如下问题:定义两个不相关的节点node_A 和 node_B,可以自己run一下。

let node_A = new ListNode(1);

let node_B = new ListNode(2);

let temp = node_A

temp.next = node_B

那么 node_A.next ?

    答案: 输出 node_B。


3. 能理解上面这一点,下面反转也就很好理解了。先附上完整的反转代码:

function ListNode(val, next) {
    this.val = (val===undefined ? 0 : val)
    this.next = (next===undefined ? null : next)
}

let head = new ListNode(1, new ListNode(2, new ListNode(3)));


let reverseList = function(head) {
    if (head == null || head.next == null) {
        return head;  // 如果链表只有一个元素或者是空链表,我们直接返回
    }
    let newHead = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return newHead;
}

reverseList(head)

理解一下这个递归过程:以原链(head  -> 1  -> 2  -> 3 为例)
1、假如当前是最后一个节点,则直接返回。 ok,那么读到三的时候直接返回


2、从倒数第二个节点开始,改变指针指向。 ok,那么读到2的时候,开始反转。如何改变指针指向呢? 用后一个节点的next指向前一个节点(用3.next  =  2 , 也就是代码里的 head.next.next = head ) , 然后 原来的2 -> 3 的方向要删掉,也就是设置为null。这里有点绕,可以画画图,用笔纸写一写。 

3、返回当前当node。



       


        

更多推荐