This article was originally published in The Language Sparrow Archive

The title

Leetcode-cn.com/problems/re…

Flow chart, debug code

Github.com/blueju/leet… /

First attempt

I can’t write it at all. I have no idea.

But it’s not difficult, you just switch the order, store the previous node, change the next of the current node to the previous node, but the tricky thing is, the first node, what was its previous node?

But it didn’t occur to me that the first node didn’t need to be skipped at all. The first node must become the last node, and its next must be null.

That makes a lot of sense.

​

Second attempt (by test case)

The flow chart

code

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} head
 * @return {ListNode}* /
var reverseList = function (head) {
    let prev = null
    let curr = head
    while (curr) {
        const next = curr.next
        curr.next = prev
        prev = curr
        curr = next
    }
    return prev
};
Copy the code

conclusion

Remember to temporarily store the next of the current curr node, otherwise the link is broken.

Third attempt

They say that in addition to iteration, you can also use recursion. To further clarify the difference between iteration and recursion and transformation, I thought I’d go ahead and try.

Okay, I tried it. I can’t write it. What’s wrong with it

conclusion

After reading the solution, I found three main points:

  1. How to return

Since we need the head node of a return to be the last node, there is only one way to do that, and that is to get the last node out of the bottom nesting

  1. How to modify pointing

We can see from the above point that the return of a recursive function is required to return all the way to the outermost layer, so it cannot be modified during the period. Usually we usually use XXX. Next is finished, but here we need to use next. Next, this is also I did not expect

​

Fourth attempt (by test case)

code

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} head
 * @return {ListNode}* /
var reverseList = function (head) {
    if (head === null || head.next === null) {
        return head
    }
    const result = reverseList(head.next)

    head.next.next = head
    head.next = null

    return result
};
Copy the code

conclusion

What recursion is, is the innermost execution first.

For example, start from the inside, work your way back, find the repeating part, then seal it, and consider boundary cases (e.g., head is null).