首页 Computer-Science Coding-Interviews

# 面试题 35：复杂链表的复制

# 题目

请实现函数 ComplexListNode *clone(ComplexListNode *pHead) ，复制一个复杂链表。在复杂链表中，每个节点除了有一个 m_next 指针指向下一个节点，还有一个 m_sibling 指针指向链表中的任意点或者 nullptr 。节点的 C++ 定义如下：

struct ComplexListNode {
    int m_value;
    ComplexListNode *m_next;
    ComplexListNode *m_random;
};

在复杂链表的节点中，除了有指向下一个节点的指针之外，还有另一个指针指向任意一个节点。

# 思路

最朴素的做法是复制原始链表上的每个节点，之后再复制 m_sibling 的指针。对于一个含有 n 个节点的链表，需要 O(n)O(n) 的时间才能定位 m_sibling 节点，因此总的时间复杂度是 O(n2)O(n^2)。

利用哈希表记录每个节点 NN 对应的复制后的节点 N^'。在复制了原始节点之后，通过 m_random 查找哈希表获取其对应的复制后的节点。如此可通过 O(1)O(1) 的时间定位对应的节点。

另一种方法是将复制后的节点直接连接在原始节点之后，在对 m_random 赋值时，通过原始节点的 m_random 指针可以定位到 m_random 的复制后的节点，即 m_random->m_next 。

# 代码

#include <iostream>
using namespace std;
struct ComplexListNode {
    int m_value;
    ComplexListNode *m_next;
    ComplexListNode *m_random;
    ComplexListNode() : m_value(-1), m_next(nullptr), m_random(nullptr) {}
};
void clone_nodes(ComplexListNode *head) {
    ComplexListNode *node = head;
    while (node != nullptr) {
        ComplexListNode *cloned = new ComplexListNode();
        cloned->m_value = node->m_value;
        cloned->m_next = node->m_next;
        node->m_next = cloned;
        node = cloned->m_next;
    }
}
void connect_random_nodes(ComplexListNode *head) {
    ComplexListNode *node = head;
    while (node != nullptr) {
        ComplexListNode *cloned = node->m_next;
        if (node->m_random != nullptr) {
            cloned->m_random = node->m_random->m_next;
        }
        node = cloned->m_next;
    }
}
ComplexListNode *reconnect_nodes(ComplexListNode *head) {
    ComplexListNode *node = head;
    ComplexListNode *cloned_head = nullptr;
    ComplexListNode *cloned_node = nullptr;
    if (node != nullptr) {
        cloned_head = cloned_node = node->m_next;
        node->m_next = cloned_node->m_next;
        node = node->m_next;
    }
    while (node != nullptr) {
        cloned_node->m_next = node->m_next;
        cloned_node = cloned_node->m_next;
        node->m_next = cloned_node->m_next;
        node = node->m_next;
    }
    return cloned_head;
}
ComplexListNode *clone(ComplexListNode *head) {
    clone_nodes(head);
    connect_random_nodes(head);
    return reconnect_nodes(head);
}
# 面试题 36：二叉搜索树与双向链表


# 题目


输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表，要求不能创建任何新的节点，只能调整树中节点指针的指向。


# 思路


在将二叉搜索树转换成排序双向链表时，原先指向左子节点的指针调整为链表中指向前一个节点的指针，原先指向右子节点的指针调整为链表中指向后一个节点的指针。由于要求转换之后的链表是排好序的，我们可以中序遍历树中的每个节点。


当遍历到一个节点时，它的左子树已经转换成了一个有序的链表，将链表和当前节点连接，接着继续转换该节点的右子树。该过程是一个递归过程。


# 代码


#include <iostream>
using namespace std;
struct BinaryTreeNode {
    int m_value;
    BinaryTreeNode *m_left;
    BinaryTreeNode *m_right;
};
void convert_node(BinaryTreeNode *node, BinaryTreeNode **last_node_of_list) {
    if (node == nullptr) {
        return;
    }
    BinaryTreeNode *current = node;
    if (current->m_left != nullptr) {
        convert_node(current->m_left, last_node_of_list);
    }
    current->m_left = *last_node_of_list;
    if (*last_node_of_list != nullptr) {
        (*last_node_of_list)->m_right = current;
    }
    *last_node_of_list = current;
    if (current->m_right != nullptr) {
        convert_node(current->m_right, last_node_of_list);
    }
}
BinaryTreeNode *convert(BinaryTreeNode *root) {
    BinaryTreeNode *last_node_of_list = nullptr;
    convert_node(root, &last_node_of_list);
    BinaryTreeNode *head_of_list = last_node_of_list;
    while (head_of_list != nullptr && head_of_list->m_left != nullptr) {
        head_of_list = head_of_list->m_left;
    }
    return head_of_list;
}
# 面试题 37：序列化二叉树


# 题目


请实现两个函数，分别用来序列化和反序列化二叉树。


# 思路


根据前序遍历的顺序来序列化二叉树，因为前序遍历是从根节点开始的。在遍历二叉树碰到  nullptr  指针时，这些  nullptr  指针序列化为一个殊的字符（如  $ ）。另外，节点的数值之间要用一个特殊字符（如  , ）分隔。


# 代码


#include <iostream>
using namespace std;
struct BinaryTreeNode {
    int m_value;
    BinaryTreeNode *m_left;
    BinaryTreeNode *m_right;
    BinaryTreeNode() : m_value(-1), m_left(nullptr), m_right(nullptr) {}
};
bool read_stream(istream &stream, int *number) {
    char c;
    bool result = true;
    int num = 0;
    while (stream >> c) {
        if (c == ',') {
            break;
        } else if (c == '$') {
            result = false;
            continue;
        } else {
            num *= 10;
            num += c - '0';
        }
    }
    if (result) {
        *number = num;
    }
    return result;
}
void serialize(BinaryTreeNode *root, ostream &stream) {
    if (root == nullptr) {
        stream << "$,";
        return;
    }
    stream << root->m_value << ',';
    serialize(root->m_left, stream);
    serialize(root->m_right, stream);
}
void deserialize(BinaryTreeNode **root, istream &stream) {
    int number;
    if (read_stream(stream, &number)) {
        *root = new BinaryTreeNode();
        (*root)->m_value = number;
        deserialize(&((*root)->m_left), stream);
        deserialize(&((*root)->m_right), stream);
    }
}
# 面试题 38：字符串的排列


# 题目


输入一个字符串，打印出该字符串中字符的所有排列。例如，输入字符串  abc ，则打印出由字符  a 、 b 、 c  所能排列出来的所有字符串  abc 、 acb 、 bac 、 bca 、 cab  和  cba 。


# 思路


求整个字符串的排列，可以看成两步。第一步求所有可能出现在第一个位置的字符，即把第一个字符和后面所有的字符交换。第二步固定第一个字符，求后面所有字符的排列。这时候仍把后面的所有字符分成两部分：后面字符的第一个字符，以及这个字符之后的所有字符。然后把第一个字符逐一和它后面的字符交换。这是典型的递归思路。


# 代码


#include <iostream>
#include <string>
using namespace std;
void permutation(string &str, int idx) {
    if (idx == str.size()) {
        cout << str << endl;
    } else {
        for (int i = idx; i < str.size(); ++i) {
            swap(str[i], str[idx]);
            permutation(str, idx + 1);
            swap(str[i], str[idx]);
        }
    }
}
void permutation(string &str) {
    if (str.empty()) {
        return;
    }
    permutation(str, 0);
}