脸熟跪经

一小时前面的脸熟，是个国人大哥，真的很放水，给了一大堆提示，然而还是跪在第二题。。

第一题是利口而起巴，写完码

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

样，第二题真的没时间准备到。应该已经gg了，攒个人品吧。

或者可以想成是二叉树的preorder嘛，s的下一层其实就是left，s的next其实就是right啊

既然是dfs 那就不能用queue吧 写了一个iterative的方法 有没有老铁讨论一下这道题 不太懂recursive的方法

struct Node{
        int val;
        Node* next;
        Node* child;
}

class Iterator {
private:
        stack<Node*> nodes;
public:
        Iterator(Node* root){
                nodes.push(root);
        }
       
        int next(){
                Node* res = nodes.top();
                nodes.pop();
                if(res->next){
                        nodes.push(res->next);
                }
                return res->val;
        }
       
        bool hasNext(){
                while(!nodes.empty()){
                        Node* curr = nodes.top();
                        if(curr->child == NULL){
                                return true;
                        }
                        nodes.pop();
                        if(curr->next){
                                nodes.push(curr->next);
                        }
                        while(curr->child){
                                nodes.push(curr->child);
                                curr = curr->child;
                        }
                }
                return false;
        }
}

第二题如果是recursive来做，不用全局的话，就先save next，然后把s的flatten之后，再找到当前tail换成next可以吗? 代码大概是这样
Node* flattenList(Node* node, Node* s)
{
    if (node == NULL)
        return NULL;
       
        Node* head = new Node(0);
        head->next = node;

        Node* cur = head;
        while (cur->next && cur->next != s) cur = cur->next;
        if (cur->next == s) {
                        Node *next = cur->next->next;
                        cur->next = flattenList(s->child);
                        if (next)
                                        while (cur->next) cur = cur->next;
                                        cur->next = flattenList(next, s);
        }

    return head->next;
}

可以请楼主第二题给个例子吗？

谢谢

楼主是第几轮面

啥情况，今天大规模店面！！没出结果，别着急

mtrsen 发表于 2017-9-27 07:50
楼主是第几轮面

第一轮 紫薯紫薯紫薯

chris612ku 发表于 2017-9-27 07:42
可以请楼主第二题给个例子吗？

谢谢

就是 1-2-3-4-s-6-7-8
                   |-9-10-11

这样的。
中间会有个特殊的node（s），然后最后不要把它连进去

楼主这第二题面经具体怎么描述的？萌新从来没看过。谢谢

zhanym0981 发表于 2017-9-27 09:15
就是 1-2-3-4-s-6-7-8
                   |-9-10-11

所以这个的意思是s node就只是代表他是连接到下一层的点，
这样output会变成是 1-2-3-4-6-7-8-9-10-11吗？
还是1-2-3-4-9-10-11-6-7-8?

谢谢

诶，投了好久到现在也没给面试通知，祝LZ好运

chris612ku 发表于 2017-9-27 10:48
所以这个的意思是s node就只是代表他是连接到下一层的点，
这样output会变成是 1-2-3-4-6-7-8-9-10-11吗 ...

1-2-3-4-6-7-8-9-10-11是对的