[leetcode] 24. Exchange nodes in the linked list in pairs

24、 Two or two exchange nodes in a linked list

subject ：

I'll give you a list , Two or two exchange the adjacent nodes , And return the head node of the linked list after exchange . You must complete this problem without modifying the value inside the node （ namely , Only node switching can be performed ）.

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]

Tips ：

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

Their thinking ：

Use recursion to solve the problem , Mainly recursive trilogy ：

1. Find termination conditions ： The termination condition of this question is obvious , When recursion arrives when the linked list is empty or there is only one element left in the linked list , There's no exchange , Naturally, it ends .
2. Find the return value ： The value returned to the upper level of recursion should be the sub linked list after the exchange is completed .
3. A single process ： Because recursion is doing the same thing repeatedly , So from a macro perspective , Just think about how a certain step is completed . We assume that the two nodes to be exchanged are head and next,next Should accept the sub linked list returned by the previous level ( Refer to the first 2 Step ). It is equivalent to a linked list with three nodes exchanging the first two nodes , It's easy , If you don't understand, draw a picture ok.

Reference code ：

class Solution {
    
    public ListNode swapPairs(ListNode head) {
    
        if(head == null || head.next == null){
    
            return head;
        }
        ListNode next = head.next;
        head.next = swapPairs(next.next);
        next.next = head;
        return next;
    }
}