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

[B] [C] [D]

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:

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

Example 2:

Input: head = [] Output: []Copy the code

Example 3:

Input: head = [1] Output: [1]Copy the code

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.)

Leetcode -25.K sets of flipped lists

If you are interested in solving leetcode-25.K groups of flipped lists, please read my previous article “Leetcode-25-K groups of flipped lists”.

In this case, we just need to find two linked list nodes, and then switch their positions, and then connect the swapped head node to the end of the result list

Here I approach the problem in two ways

Answer key 1

Through the recursive way to complete the original linked list in pairs

  1. First we need oneswapFunction to do our recursive logic
  2. This function first determines whether the remaining list to be processed has two nodes, and if not, returns directlyheadCan be
  3. The third (possibly empty) node passed into the list is recorded first, which is the head node of the list to be processed later
  4. Swap the incoming linked listheadandhead.nextAt this time,head.nextSwapped the head node of the linked list
  5. Connect the head node returned after the subsequent linked list processing is complete toheadAfter the node (because nowheadNode is the second node after switching)
  6. Return the head node after the switch

The code is as follows:

/ / will be introduced to list first, the second node exchange, and recursive processing subsequent list function swap (head) {/ / if the linked list node number is not enough 2, direct return if (head = = = null | | head. The next = = = null) return the head;  Const nextHead = head.next-next, vhead = new ListNode(0); // Record the head node of the next list const nextHead = head.next-next, vhead = new ListNode(0); // Record the head node to return vhead.next = head.next; // Switch two nodes head.next-next = head; Next = swap(nextHead) // Return vhead.next; } var swapPairs = function(head) {return swapPairs (head); };Copy the code

Answer key 2

Directly in the linked list traversal process

  1. If the number of input linked list nodes is less than two, return the original linked list
  2. When there are two remaining nodes in the list to be processed, record the third node (the head node of the subsequent list to be processed).
  3. Swap the two nodes for this process and connect the swapped head node to the end of the result list
  4. Update the first node pointer to the head node of the subsequent list to be processed
  5. Check if there is a second node, if so, update the second node pointer to the second node, otherwise point tonull
  6. When the list is less than two, determine whether the first node pointer points to the real node and, if so, concatenate it to the end of the resulting list
  7. Return the result list head node

The code is as follows:

Var swapPairs = function (the head) {/ / if the input list node number less than two, return to the original list if (head = = = null | | head. The next = = = null) return the head; const vhead = new ListNode(0); let pre = vhead, tail = head, next = head.next; // While (tail&&next){// Record the third node const nextHead = next-next; // Switch two nodes next. Next = tail; tail.next = null; // Connect the swapped head node to the end of the result list. // Update pointer pre = tail; tail = nextHead; next = tail? tail.next:null; } // If the last tail pointer points to a real node, connect it to the end of the result list if(tail) pre-next = tail; // Return vhead.next; };Copy the code

We have now completed the nodes in the Leetcode-24-pair-swap linked list

If you have any questions or suggestions, please leave a comment!