This is the 24th day of my participation in the August Text Challenge.More challenges in August

The title

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]

 

Tip:

  • The number of nodes in the linked list is in range[0, 100] 内
  • 0 <= Node.val <= 100 

** Advanced: ** Can you solve this problem without changing the value of the linked list node? (That is, only the node itself is modified.)

Their thinking

Idea 1

  • Set dummy to dummy. Dummy. Next finds dummy.
  • When we start the while loop, the exchange of a pair of nodes has three Pointers to change, as shown below.
  • Pointer advances, ready to swap the next pair of nodes.
  • Finally, dummy.next is returned.

code

const swapPairs = (head) = > {
  const dummy = new ListNode(0);
  dummy.next = head;
  let prev = dummy;

  while (head && head.next) {
    const next = head.next; // Temporarily save head. Next because head. Next will change later
    head.next = next.next;
    next.next = head;
    prev.next = next;  

    prev = head;      // Update the pointer
    head = head.next; // Update the pointer
  }
  return dummy.next;
};
Copy the code

Idea 2: Non-recursion

  • Time complexity: O(n)
  • Space complexity: O(1)
  • Train of thought
  • Add a sentinel node
  • Three nodes plus one sentinel node for pointer conversion operation
  • The illustration
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/ * * *@param {ListNode} head
 * @return {ListNode}* /
var swapPairs = function(head) {
    let thead = new ListNode(0);
    thead.next = head;
    let tmp = thead;
    while(tmp.next ! =null&& tmp.next.next ! =null) {let start = tmp.next;
        let end = start.next;
        tmp.next = end;
        start.next = end.next;
        end.next = start;
        tmp = start;
    }
    return thead.next;
};
Copy the code

Idea 3: Recursion

  • Time complexity: O(n)
  • Space complexity: O(n)
  • Train of thought
  • Termination of
    • Same solution 1: at least three nodes can be interchangeable
    • Returns this node with only one node or no node
  • exchange
    • Set the two nodes to be swapped as head and next
    • head -> next -> c -> …
    • head -> c -> … && next -> head
    • next -> head -> c -> …
      • Head joins (->) after swapping completed sublists
      • Next joins (->)head to complete the swap
    • Repeat the process for the sublists
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/ * * *@param {ListNode} head
 * @return {ListNode}* /
var swapPairs = function(head) {
    if(head == null || head.next == null) {return head;
    }
    // Get the second node
    let next = head.next;
    // next.next = head.next.next
    // The first node points to the third node and recurses from the third node
    head.next = swapPairs(next.next);
    // The second node points to the first node
    next.next = head;
    // or [head. Next,next. Next] = [swapPairs(next.
    return next;
};
Copy the code

The last

I dreamed of traveling with swords

Look at the prosperity of the world

Young heart always some frivolous

Just a man after all

No regrets I go my way

“Front brush” No.24