LeetCode algorithm learning - list - two exchange

Today, I would like to share with you the next LeetCode medium difficulty topic [exchange nodes in two linked lists](leetcode-cn.com/problems/co...).

Here is mainly to share ideas and comments, for you to better understand the problem solution, the code part is to refer to LeetCode translated into javascript code,

The title

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

You can't just change the values inside a node, but actually switch nodes. (Image from Leetcode)

Example 1: Input: head = [1,2,3,4] Output: [2,1,4,3] Example 2: Input: head = [] Output: [] Example 3: Input: head = [1] Output: [1]Copy the code

Analysis of the

1. Pairwise exchange can be pointer + iteration

2. Use recursion

Solution a:Iteration + double pointer

Code reprint leetcode-cn.com/problems/sw...

Train of thought1.continuous3The number is a group2.Since three numbers are required, a dummy number is required3.Swap positions in the loop, and then move a temp pointer3.When the temp. Next = = =nullAnd when the temp. Next. Next = = =nullEnds the loop */var swapPairs = function (head) {
  const dummy = new ListNode(0);
  dummy.next = head;
  let temp = dummy;

  Next ==null when the list is even; next ==null when the list is odd
  // Note that this must be  because you want to make sure you are in pairs
  while(temp.next ! = =null temp.next.next ! = =null) {
    // List the two points that need to be exchanged
    const node1 = temp.next;
    const node2 = temp.next.next;

    // Switch the location of the node
    temp.next = node2;
    node1.next = node2.next;
    node2.next = node1;
    temp = node1;
  }

  return dummy.next;
};

/* Complexity time O(n) space O(1) */

Copy the code

Method 2:recursive

Code reprint leetcode-cn.com/problems/sw...

Train of thought1.When the list is even, the last Head isnull【1.2】, such as2.Next tonullIs odd when head.next isnull, such as [1.2.3] 2.Next, next tonull

2.Things you do inside the recursion1.Stores the value temp for the next node2.Next points to the switched node3.Temp pointing in the direction of the head4.Returns the temp * /var swapPairs = function (head) {
  if (head === null || head.next === null) {
    return head;
  }

  const temp = head.next;
  head.next = swapPairs(temp.next);
  temp.next = head;
  return temp;
};

/* Complexity time O(n) space O(n) */
/ *Copy the code

conclusion

This question is about understanding the movement of the pointer in a linked list, and you can do it recursively and iteratively.

You can look at a column I share (front-end algorithm) there are more questions about the algorithm to share, I hope to help you, I will try to keep updated every night, if you like the trouble to help me a like, thank you very much

The purpose of this article is to study, discuss and share the experience in the process of learning algorithm. Part of the material in this article comes from the network. If there is infringement, please contact delete, [email protected]