The thesis implements pally switching of nodes in a linked list

Given a linked list, swap adjacent nodes in pairs and return the swapped list.

You can’t just change the value inside the nodeInstead, you need to actually swap nodes.

Example:

Resolution:

Suppose we disregard the fact that you can’t just change the value ** inside a node, but need to actually swap nodes. This sentence, we realize very easy. We could have done a simple implementation here, but that’s not the way they’re going to do it.

var swapPairs = function(head) {
    let p = head
    let index = 0
    while(p) {
        if(index % 2 === 0 && p.next) {
            let val = p.val
            p.val = p.next.val
            p.next.val = val
        }
        index++
        p = p.next
    }
    return head
};
Copy the code

The results are completely consistent, and the submission detection can also pass, but how should we achieve it if we switch nodes according to the requirements?

Emphasis: the so-called exchange of nodes rather than the exchange of internal values means that the purpose of exchanging nodes is to change the Pointers of nodes rather than the contents of nodes.

Use iterative method for replacement, steps:

  1. Set the virtual node in front of head
  2. Set the next node of the virtual node to Node1 and the next node to Node2
  3. Point the virtual node next to Node2
  4. Point next on Node1 to Next on Node2
  5. Point Node2’s next to Node1
  6. Set Node1 to the new virtual node
  7. Repeat the above steps

Is it confusing and confusing to see? So look at the picture:

Is that obvious? This implements the first swap and resets the position of the virtual node. The call can be completed in sequence.

Boundary problem: the virtual node ends when the next node does not exist. That’s not hard to think about.

Implementation 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 swapPairs = function(head) { // let p = head //  let index = 0 // while(p) { // if(index % 2 === 0 && p.next) { // let val = p.val // p.val = p.next.val // p.next.val =  val // } // index++ // p = p.next // } // return head // }; var swapPairs = function(head) { let tempNode = new ListNode(0) tempNode.next = head let temp = tempNode while(temp.next  && temp.next.next) { let node1 = temp.next let node2 = temp.next.next temp.next = node2 node1.next = node2.next node2.next = node1 temp = node1 } return tempNode.next };Copy the code

Such an exchange is possible, but how to think of such an exchange? There is no way, can only look at similar linked list exchange of questions, which is equal to white, but it is really the truth!