This is the 18th day of my participation in the August Challenge

preface

Today, it is still a linked list problem in LeetCode. It is interesting to exchange the nodes in the linked list in pairs. To do the linked list problem, we must make clear whose next is who, and the logic must be clear, otherwise we will be confused when doing it

Topic describes

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

You can’t just change the values inside a node, you need to actually swap nodes.

 

Example 1:

Enter: head = [1,2,3,4]

Output:,1,4,3 [2]

Example 2:

Enter: head = []

Output: []

Example 3:

Enter: head = [1]

Output: [1]

Their thinking

  • We know from the problem that if we think of this list as an array, it swaps subscripts (1,2) (3,4)… If you end up with only one term, you don’t switch
  • In this problem we need to define three Pointers, and we need at least three arguments to swap two numbers in a sorted array
  • Want to do in the beginning we deal with this problem, because began to change, also is the first node and the second node exchange, we also need a pointer p, at this time not eligible at this time node can be used to make p points to, so if we need to use to judge for the first and the second node to transfer, or declare a dummy to point to the head, Then we can point p to this node, and we can switch the first node and the second node, as follows
/ * * *@param {ListNode} head
 * @return {ListNode}* /
var swapPairs = function(head) {
    let dummy = new ListNode()
    dummy.next= head
    let p = dummy
    while(p.next! = =null&& p.next.next! = =null) {// Stop the loop when one of the items is empty
        // Complete a swap by following the 6 steps below and move the three Pointers P,n1,n2 to the desired position next time
        let n1 = p.next
        let n2 = p.next.next
        // The walk below is a real switch
        p.next = n1.next
        n1.next = n2.next
        n2.next = n1
        // Move p to the first of the two nodes to be swapped next time
        p = n1
    }
    return dummy.next // finally return dummy. Next instead of dummy
};
Copy the code

LeetCode run result

conclusion

Two nodes in the linked list exchange is roughly like this, the most important idea or conditioning clear, if you have advice welcome comments, gogogo