I’ve written about list inversion before, but looking at the previous article, it feels too brief, just Posting the code, and not telling the core stuff. Take advantage of the weekend, let’s go over this simple problem again.

How do I reverse an array?

As we all know, JavaScript arrays provide a number of useful methods for manipulating arrays, including array.prototype. reverse, which reverses the numbers in an Array. It’s easy to use the reverse function to reverse an array. Here’s how the code works:

let array = [1.2.3.4.5]
array.reverse()     // [5, 4, 3, 2, 1]
Copy the code

The code is simple, but we still don’t know how to reverse it. Here’s the next common idea: ———— header/tail swap, as shown below:

  • 1
  • 2
  • 3
  • 3
  • 2
  • 1

Array length is 4:

  • 1
  • 2
  • 3
  • 4
  • 4
  • 2
  • 3
  • 1
  • 4
  • 3
  • 2
  • 1

Array length is 5:

  • 1
  • 2
  • 3
  • 4
  • 5
  • 5
  • 2
  • 3
  • 4
  • 1
  • 5
  • 4
  • 3
  • 2
  • 1

So an array of length n needs to be swapped n / 2 + 1 times, which gives us the following code:

let array = [1.2.3.4.5]
for(let i = 0; i < array.length / 2; i ++){
    [array[i], array[array.length - i - 1]] = [array[array.length - i - 1], array[i]]
}
console.log(array)  // [5, 4, 3, 2, 1]
Copy the code

How do I reverse linked lists?

What is a linked list? A chain structure of length N, which cannot be traversed by subscript, can only be accessed through the current node to the next node. So without further ado, let’s construct a simple linked list:

// Node constructor
function Node(val){
    this.val = val
    this.next = null
}
// Define the linked list
function List(array){
    this.head = null
    let i = 0,temp = null
    while(i < array.length){
        if( i === 0) {this.head = new Node(array[i])
            temp = this.head
        }else{
            let newNode = new Node(array[i])
            temp.next = newNode
            temp = temp.next
        }
        i++
    }
}
// Iterate over the list
function traverseList(listHead){
    while(listHead){
        console.log(listHead.val)    
        listHead = listHead.next
    }
}
Copy the code

The above is a simple implementation of a linked list, do not understand the friends can look at the data structure and algorithm next underline: The linked list can only be accessed by the current node to the next node, and can not be accessed by subscript. At first, I didn’t think of a way, but later I used a strange method ———— to store the value of the linked list into an array, and then invert the array and re-assign the value, the code is as follows:

/** * @param {ListNode} head * @return {ListNode} */
var reverseList = function (head) {
    let temp = head,
        result = []
    while(temp ! =null) {
        result.push(temp.val)
        temp = temp.next
    }
    temp = head, i = 0
    result.reverse()
    while(temp ! =null) {
        temp.val = result[i++]
        temp = temp.next
    }
    return head
};
Copy the code

But this obviously doesn’t take advantage of the linked list feature ———— where the current node accesses the next node. Later I saw this idea in a discussion in LeetCode ———— local inversion constitutes global inversion what does that mean? Such as:

  • 1
  • 2
  • 3
  • 4
  • 2
  • 1
  • 3
  • 4
  • 3
  • 2
  • 1
  • 4
  • 4
  • 3
  • 2
  • 1
var reverseList = function (head) {
    let pre = null
    while (head) {
        next = head.next
        head.next = pre
        pre = head
        head = next
    }
    return pre
};
Copy the code

Is the idea simple? It’s a simple idea that I didn’t think of at the time… Reflection ing…

conclusion

From array inversion to linked list inversion, we can draw a conclusion: thinking can not be rigid (escape, a seemingly common algorithm ———— inversion, there can be many ways. If you know any other algorithms, please advise

Scan the QR code below or search for “Teacher Tony’s front-end cram school” to follow my wechat official account, and then you can receive my latest articles in the first time.