【牛客网刷题】经典题型，确定不来看看？.

🧸🧸🧸各位巨佬大家好，我是猪皮兄弟🧸🧸🧸

废话不多说，直接来做题！！

一、📖链表分割

newcoder链表分割

思路:malloc一个新的头，将比x小的结点依次链接在后面，并且，定义一个prev可以将原链表的移走结点的其他结点连起来，最后，将两个链表链接起来返回就可以了

class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        // write code here
        ListNode* newhead=(ListNode*)malloc(sizeof(ListNode));
        ListNode*tail=newhead;
        ListNode*prev;
        newhead->next=nullptr;
        ListNode*cur=pHead;
        while(cur)
        {
            if(cur->val<x)
            {
                if(cur==pHead)
                {
                    tail->next=pHead;
                    pHead=pHead->next;
                    cur=pHead;
                    tail=tail->next;
                }
                else
                {
                    tail->next=cur;
                    prev->next=cur->next;
                    cur=cur->next;
                    tail=tail->next;
                }
            }
            else
            {
                prev=cur;
                cur=cur->next;
            }
        }
        tail->next=pHead;
        ListNode*ret=newhead->next;
        free(newhead);
        return ret;
        
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

二、📖二叉树层序遍历

nowcoder求二叉树的层序遍历
使用队列来辅助就可以了,注意size是会变的，一定要先记录size

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型vector>
     */
    vector<vector<int> > levelOrder(TreeNode* root) {
        vector<vector<int>> vv;
        if(!root){
            return vv;
        }
        queue<TreeNode*> qq;
        qq.push(root);
        while(!qq.empty()){
            vector<int> tempv;
            int size=qq.size();
            for(int i=0;i<size;++i){
                TreeNode* tt=qq.front();
                qq.pop();
                tempv.push_back(tt->val);
                if(tt->left)qq.push(tt->left);
                if(tt->right)qq.push(tt->right);
            }
            vv.push_back(tempv);
        }
        return vv;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

三、📖对称的二叉树

nowcoder对称的二叉树

class Solution {
public:
    
    bool isRSameTree(TreeNode*root1,TreeNode*root2)
    {
        if(root1==nullptr&&root2==nullptr)
            return true;
        if(root1==nullptr||root2==nullptr||root1->val!=root2->val)
            return false;[
](https://www.nowcoder.com/practice/a9d0ecbacef9410ca97463e4a5c83be7?tpId=295&tqId=1374963&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=/exam/oj)
    
      return (isRSameTree(root1->left,root2->right)&&
              isRSameTree(root1->right,root2->left));

    }
    bool isSymmetrical(TreeNode* pRoot) {
        if(pRoot==nullptr)
            return true;
        return isRSameTree(pRoot->left,pRoot->right);
    }

};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

四、📖二叉树的镜像

nowcoder二叉树的镜像

    TreeNode* Mirror(TreeNode* pRoot) {
        if(pRoot) //判断边界条件，是否为空树 空树递归结束
        {
            /*交换*/
            TreeNode* temp;//定义一个缓冲指针
            temp=pRoot->left;//缓冲左树
            pRoot->left=pRoot->right;//左树等于右树
            pRoot->right=temp;//右树等于左树（缓冲）
            /*递归*/
            pRoot->left=Mirror(pRoot->left);//递归左树
            pRoot->right=Mirror(pRoot->right);//递归右树
        }
        return pRoot;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

五 、📖牛客oj总结

牛客网是个很不错的刷题软件，也希望大家能天天在上面刷刷题，大厂offer指日可待啊兄弟们。刷起来。