Subject to introduce

Given a linked list, swap adjacent nodes in pairs and return the head of the swapped list. You must do this without changing the values inside the nodes (that is, swapping nodes only).

Example 1

Enter: head = [1.2.3.4] output: [2.1.4.3]
Copy the code

Example 2

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

Example 3

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

Leetcode -24 pin-pin-switch link list in the node B station video

Their thinking

Iterative method

The iterative method is to walk through all the nodes of the list, and when two adjacent nodes can be paired, the position between the two nodes is changed

1. Define a virtual head node. The next node of the virtual head node points to head node 2. Define pre to point to the virtual head node and cur to point to head node 3. When cur and cur.next existed, Next 4. The next node of pre points to next 5. The next node of next points to the next node of Next 6. Cur points to the next node of cur, 8. Repeat 3-7 until the list ends

The problem solving code

var swapPairs = function(head) {
    if(! head || ! head.next)return head
    const newNode = new ListNode(-1, head)
    let pre = newNode
    let cur = head, next
    while (cur && cur.next) {
        next = cur.next
        pre.next = next
        cur.next = next.next
        next.next = cur
        pre = cur
        cur = cur.next
    }
    return newNode.next
};
Copy the code

The recursive method

Recursion requires finding the conditions for the end of recursion and the recursive process

In the current problem, the recursion process is the exchange between the odd number node and the next even number node, and the recursion ends when the current node or the next node of the current node is empty, that is, the nodes are not paired

1. Check whether the current node or the next node of the current node is empty. If it is empty, the current node 2 is returned. Define the next pointer to point to the next node of the current node. 3. Assuming that all subsequent pairs have been swapped except for the current pair, the next node of the current node should point to the head of the reversed list. Returns the node to which the next pointer points, the head of the list after inversion

The problem solving code

var swapPairs = function(head) {
    if(! head || ! head.next)return head
    const next = head.next
    head.next= swapPairs(next.next)
    next.next = head
    return next
};
Copy the code

[lufei]_ ring list [Lufei]_ ring list II [Lufei]_ happy number [Lufei]_ reverse list II [Lufei]_ REVERSE list [Lufei]_K group of flip list [Lufei]_ rotation list