My first day learning animation with Uncle Ran

How does JS swap nodes in a linked list

Give you the head node of the list, head, and an integer k.

After swapping the value of the positive and penultimate KTH node of the list, return the head node of the list (the list is indexed from 1).

Example:

Input: head = [1,2,3,4,5], k = 2 output: [1,4,3,2,5]Copy the code

When k = 2, the position of the second and penultimate node in the linked list is switched, that is, the position of 2 and 4 is switched. However, it is worth noting that the next reference of the second node in the linked list remains unchanged, pointing to 3, and the next reference of the fourth node remains unchanged, pointing to 5. It is important to understand that this is the val value of the swap node.

Based on the above analysis, we can break it down as follows:

  1. Find the KTH node
  2. Find the penultimate KTH node
  3. Swap their val values

1. Find the KTH node

Let p be a pointer to the linked list and walk through the list. If count === k, the node to which p pointer points is the KTH node

As follows:

2. Find the penultimate KTH node

This is an interesting way to find the list, because we know that the length of the list can only be found by going from the beginning to the end, so how do we find the KTH node to the end? You can actually find it by counting synchronous traversal. Here’s how it works:

So let’s say I’m looking for the last to last node, so we know it’s the last node, when the list goes to the end.

If I were looking for the next-to-last node, my pointer would have to move count – 2 to find it, and so on.

If not, use the following diagram to illustrate:

So the code above continues to implement

As follows:

2. Swap val values

Find an intermediate variable and swap it as follows:

Complete code:

var swapNodes = function (head, K) {// set count = 1 // set traversal pointer let p = head // define KTH node let front = null // define KTH node let back = head while (p) { If (count === k) {if (count === k) {front = p} If (count > k) {back = back.next} p = p.ext count++} val let temp = front.val front.val = Back. Val back. Val = temp // return return head};Copy the code

The above is to solve the idea and process of switching linked list specified nodes. PS: this algorithm is not important, suddenly feel the animation exquisite, 5 minutes to solve the problem, animation 2 hours!! So you must understand!!