This is the 21st day of my participation in Gwen Challenge

preface

The nodes in the p2-p2 switching linked list are as follows:

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]

Example 2:

Input: head = [] Output: []

Example 3:

Input: head = [1] Output: [1]

A, thinking

To replace two or two nodes in a linked list, the simple idea is to traverse the list from left to right, swapping whenever two nodes are encountered.

The above traversal form, in fact, can also be achieved by recursion in the linked list of adjacent nodes exchange. The specific steps are as follows:

Assume the following: head: initializes the first node of the original linked list temp: temporary variable

  • If the list to which head points does not have two nodes, head is returned directly
  • Temp = head.next, pointing to a node after head
  • Start the recursion temp.next (since the first two elements have already been processed, the third element needs to be processed here)
  • Next = head, and then temp.next points to the head to be processed

Here’s an example:

Assume the linked list is 1->2->3->4->5

  1. headStart point to1(1 – > 2 – > 3 – > 4 – > 5)
  2. tempPoint to the2, 4 – (2 – > 3 – > > 5)
  3. Recursive processingtemp.next, that is, processing 3->4->5, the final recursive return result is 4->3->5
  4. I’m going to give you the recursive resulthead.next, head is still not 1, but the entire list is 1->4->3->5
  5. thentemp.next = head.next, that is, the linked list pointed to by temp becomes4 – > 2 – > 1 – > – > 5

Second, the implementation

As mentioned above, there are two ways to achieve it. Iteration and recursion, I think iteration is easier to understand, and recursion is more about knowing when to start recursion.

The iteration

The implementation code

Ret: result set Temp: a temporary variable used to store the results of the swap tips: Since the first node of RET is null during initialization, ret.next is returned when the result is returned

    /** ** /
    public ListNode swapPairs(ListNode head) {
        ListNode ret = new ListNode();
        ListNode temp = ret;
        while(head ! =null) {
            if(head.next ! =null) {
                temp.next = new ListNode(head.next.val);
                temp = temp.next;
                temp.next = new ListNode(head.val);
                temp = temp.next;
                head = head.next.next;
            } else {
                // If there are no two elements, place the current value at the end
                temp.next = new ListNode(head.val);
                break; }}return ret.next;
    }
Copy the code

The test code

    public static void main(String[] args) {
        new Number24().swapPairs(new ListNode(1.new ListNode(2.new ListNode(3.new ListNode(4.new ListNode(5))))));
    }
Copy the code

The results of

recursive

The implementation code

Variable Description Temp: indicates a temporary variable

    /** ** **
    public ListNode swapPairs(ListNode head) {
        // Termination condition: the current node is empty or there is no next
        if (head == null || head.next == null) {
            return head;
        }
        ListNode temp = head.next;
        head.next = swapPairs(temp.next);
        temp.next = head;
        return temp;
    }
Copy the code

The results of

Third, summary

Can’t help but sigh, recursion write also too cool!

Thank you to see the end, very honored to help you ~♥