一、两两交换链表中的节点

题意：

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

input

head = [1,2,3,4]

output

[2,1,4,3]

input

head = [1]

output

[1]

思路：

可以通过递归的方式实现两两交换链表中的节点。
递归的终止条件是链表中没有节点，或者链表中只有一个节点，此时无法进行交换。

代码实现：

/* 
	A-B-C => B-A-C
 设需要交换的两个相邻节点为 A,B
*/
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
   		 //没有节点或者链表中只有一个节点 返回
        if (head == nullptr || head->next == nullptr)    return head;
        //定义一个中间值等于B节点
        ListNode* newHead = head->next;
        //A节点nex等于 C节点递归后的结果
        head->next = swapPairs(head->next->next);
        //B节点nex等于A
        newHead->next = head;
        return newHead;
    }
};

二、二叉树的层序遍历

题意：

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

input

root = [3,9,20,null,null,15,7]

output

[[3],[9,20],[15,7]]

思路

首先根元素入队
当队列不为空的时候
求当前队列的长度 n
​依次从队列中取 n个元素进行拓展，然后进入下一次迭代

代码实现：

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        if(root==nullptr) return ans;
        queue<TreeNode*>q;
        q.push(root);
        while(!q.empty()){
            int n = q.size();
            ans.push_back(vector<int> ());
            
            for(int i=0;i<n;i++){
                auto x = q.front();
                ans.back().push_back(x->val);
                auto l = x->left;
                auto r = x->right;
                if(l != nullptr) q.push(l);
                if(r != nullptr) q.push(r);
                q.pop();
            }
        }
        return ans;
    }
};