“This is the 11th day of my participation in the Gwen Challenge in November. See details: The Last Gwen Challenge in 2021”

Swap nodes in a linked list

Power button link

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 1:

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

Example 2:

Input: the head =,9,6,6,7,8,3,0,9,5 [7], k = 5 output:,9,6,6,8,7,3,0,9,5 [7]Copy the code

Example 3:

Input: head = [1], k = 1 output: [1]Copy the code

Example 4:

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

Example 5:

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

Double pointer

Train of thought

  • Just swap the values of the nodes
  • Find two nodes

Here we use double Pointers to find two nodes, and we declare two nodes fast and slow

Find the KTH node through the linked list k times, save the KTH node with tar variable

Continue traversing backwards from fast to the end and slow starts to move at the same time. When fast points to the last node, slow points to the KTH node to the last

Finally, swap the tar and slow nodes and return the head node

var swapNodes = function(head, k) {
    var fast = slow = head
    while(--k){
        fast = fast.next
    }
    var tar = fast
    while(fast.next){
        fast = fast.next
        slow = slow.next
    }
    var temp = tar.val
    tar.val = slow.val
    slow.val = temp
    return head
};
Copy the code

Array + traversal => Advanced node replacement

Train of thought

When we want to swap two nodes in a linked list, we need to consider

  • We just swap the values of the two nodes, but here we’re trying to swap the two nodes directly
  • Find the corresponding node in the linked list, and the corresponding upper and lower nodes (need to change the direction later)
  • Treatment of boundary

Here I use an array to hold each node, so that the array’s subscript is the location of each node

So the subscripts of the interchange of positive k and reciprocal k are k minus 1 and n minus k, respectively

So let’s just swap these two subscripts in the array

You just need to deal with the next pointer

Next = null; next = null; next = null

Just return the header

var swapNodes = function(head, k) {
    if(! head)return head
    var stack = []
    while(head){
        stack.push(head)
        head = head.next
    }
    var n = stack.length
    var temp = stack[k-1]
    stack[k-1] = stack[n-k]
    stack[n-k] = temp
    for(var i=0; i<n-1; i++){ stack[i].next = stack[i+1]
    }
    stack[n-1].next = null
    return stack[0]};Copy the code