Reverse linked list (Question 206)

The title

Defines a function that inputs the head node of a linked list, inverts the list, and outputs the head node of the inverted list.

Example:

Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULLCopy the code

Limitations:

  • 0 <= Number of nodes <= 5000

link

Leetcode-cn.com/problems/fa…

explain

In fact, my understanding of the list has been wrong, according to the online tutorial, the essence of a list seems to be an array, an array of elements, as follows:

[{
 val: 1,
 next: 2,
}, {
 val: 2,
 next: 3,
}, {
 val: 3,
 next: null
}]
Copy the code

But it’s not. The nature of a linked list is a little bit like a tree. It goes like this:

{
  "val": 1,
  "next": {
    "val": 2,
    "next": {
      "val": 3,
      "next": {
        "val": 4,
        "next": {
          "val": 5,
          "next": null
        }
      }
    }
  }
}
Copy the code

Each next contains all the remaining contents. For example, if this is a linked list of five sets of data, then next of the first element contains all the remaining four sets of data, and next of the second element contains all the remaining three sets of elements. This is a linked list.

My own solution

var newReverseList = function(head) { var newList = {} var arr = [] if (! head) return null function getNode(list) { if (list ! == null) { arr.push(list.val) getNode(list.next) } } getNode(head) function addNode(index) { if (index >= 0) { return { val: arr[index], next: addNode(index - 1) } } else { return null } } newList = addNode(arr.length - 1) return newList };Copy the code

The first option is to define a method that retrieves all the val values in the list and then recursively writes them to the new list, thus reversing the effect of the list.

But it’s O(2n), which is a lot of time, and it’s still some simplified code, otherwise it’s going to be a lot more time, but it looks pretty normal for a beginner.

A better answer

var newReverseList = function(head) { if (! head || ! head.next) return null var cur = head; var pre = null; while (cur) { var next = cur.next; cur.next = pre; pre = cur; cur = next } return pre };Copy the code

This answer was hard for me to understand, because of the special structure of the list, this operation was impossible to understand, and it took several attempts to print it out.

First, the code if judgment is not explained, in order to exclude some special cases, the following is the focus.

First, two variables are declared, cur for the current list, pre for the reversed list.

Then while loops over the cur variable. Inside the loop, first take out next for cur, and then assign the next attribute for cur to pre. We then assign pre to the pre changed to next, and finally, we assign cur to its next attribute.

After that, we start to cycle, expand cur layer by layer, and add value to pre layer by layer. Pre increases from inside to outside, while CUR decreases from outside to inside, which also fits the theme of linked list inversion.




PS: To view past articles and titles, click on the link below:

Here’s 👇 by date

Front Brush path – Directory (Date classification)

After some friends remind, the feeling should also be classified according to the type of questions here is in accordance with the type of 👇

Front brush problem path – Catalogue (Question type classification)

Those who are interested can also check out my personal homepage 👇

Here is RZ