Nuggets team number online, help you Offer impromptu! Click for details

Topic describes

Reverse a single linked list. Advancements: You can iterate or recursively reverse linked lists. Can you solve the problem in two ways?

Their thinking

Two ways:

  1. Pointer method, as shown:

We need to define three Pointers:

  • Define the pointer pre, which points to null
  • Define the pointer cur as the head node of the region to be reversed
  • Define the pointer next as cur.next
  • Cur. Next points to pre, pre = cur, cur = cur.next;
  1. recursive

The worst thing about recursion is to spread it out in your head, and when you do, your brain goes into chaos. I’ll write the recursion below, and then I’ll write a comment in the code that says what each line means.

The problem solving code

/ / pointer method
var reverseList = function (head) {
    if(! head || ! head.next)return head;
    let [pre, cur, p] = [null, head, head.next];
    while (cur) {
        [cur.next, pre, cur] = [pre, cur, cur.next]
    }
    return pre;
};

/ / the recursive method
var reverseListFn = function (head) {
    if(! head || ! head.next)return head;
    // The p value must be head. Next = the end of the list
    let tail = head.next, p = reverserListFn(head.next);
    // The last digit in the list points to the first digit
    tail.next = head;
    // This is to break the link of the original list and avoid forming a circular list
    head.next = null;
    return p;
};
Copy the code

conclusion

Recursion should never unfold in your head…… And I’m going to do a bunch of problems on binary trees, just to get a better idea of recursion. By the way, here to add, IT took me a long time to write this article, because I do not know how to do the GIF, the above pointer method GIF was made by myself with PPT, made all afternoon…