首页 Computer-Science Coding-Interviews

# 面试题 22：链表倒数第 kk 个节点

# 题目

输入一个链表，输出该链表中倒数第 kk 个节点。为了符合大多数人的习惯，本题从 11 幵始计数，即链表的尾节点是倒数第 11 个节点。例如，一个链表有 66 个节点，从头节点开始，它们的值依次是 11、22、33、44、55、66。这个链表的倒数第 33 个节点是值为 44 的节点。链表节点定义如下：

struct ListNode {
    int m_value;
    ListNode *m_next;
};

# 思路

假设整个链表有 nn 个节点，那么倒数第 kk 个节点就是从头节点开始的第 n−k+1n-k+1 个节点。如果我们能够得到链表中节点的个数 nn 那么只要从头节点开始往后走 n−k+1n-k+1 步就可以了。

定义两个指针。第一个指针从链表的头指针幵始遍历向前走 k−1k-1 步，第二个指针保持不动；从第 aa 步幵始，第二个指针也开始从链表的头指针开始遍历。由于两个指针的距离保持在 k−1k-1，当第一个（走在前面的）指针到达链表的尾节点时，第二个（走在后面的）指针正好指向倒数第 kk 个节点。

# 代码

#include <iostream>
using namespace std;
struct ListNode {
    int m_value;
    ListNode *m_next;
};
ListNode *find_kth_to_tail(ListNode *head, unsigned int k) {
    ListNode *fast = head;
    ListNode *slow = head;
    for (unsigned i = 0; i < k; ++i) {
        fast = fast->m_next;
    }
    while (fast->m_next != nullptr) {
        fast = fast->m_next;
        slow = slow->m_next;
    }
    return slow;
}
# 面试题 23：链表中环的入口节点


# 题目


如果一个链表中包含环，如何找出环的入口节点？


# 思路


使用双指针的方法。详情参考链接。


# 代码


#include <iostream>
using namespace std;
struct ListNode {
    int m_value;
    ListNode *m_next;
};
ListNode *meeting_node(ListNode *head) {
    ListNode *slow = head, *fast = head;
    while (fast != nullptr) {
        slow = slow->m_next;
        if (fast->m_next == nullptr) {
            return nullptr;
        }
        fast = fast->m_next->m_next;
        if (slow == fast) {
            ListNode *ptr = head;
            while (ptr != slow) {
                ptr = ptr->m_next;
                slow = slow->m_next;
            }
            return ptr;
        }
    }
    return nullptr;
}
# 面试题 24：反转链表


# 题目


定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。链表节点定义如下：


struct ListNode {
    int m_value;
    ListNode *m_next;
}
# 思路


略。


# 代码


#include <iostream>
using namespace std;
struct ListNode {
    int m_value;
    ListNode *m_next;
    ListNode() {
        m_value = -1;
        m_next = nullptr;
    }
};
ListNode *reverse_list(ListNode *head) {
    ListNode dummy;
    dummy.m_next = head;
    ListNode *prev = &dummy;
    ListNode *cur = head;
    while (cur != nullptr) {
        ListNode *next = cur->m_next;
        cur->m_next = prev->m_next;
        prev = cur;
        cur = next;
    }
    return prev->m_next;
}
# 面试题 25：合并两个排序的链表


# 题目


输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。链表节点定义如下:


struct ListNode {
    int m_value;
    ListNode *m_next;
};
# 思路


类似于归并排序。需要注意的是，当某一个链表的元素已经遍历完毕时，仍然需要将另一个链表的元素继续合并到链表中。


# 代码


#include <iostream>
using namespace std;
struct ListNode {
    int m_value;
    ListNode *m_next;
    ListNode() {
        m_value = -1;
        m_next = nullptr;
    }
};
ListNode *merge_list(ListNode *head1, ListNode *head2) {
    if (head1 == nullptr) {
        return head2;
    }
    if (head2 == nullptr) {
        return head1;
    }
    ListNode dummy;
    ListNode *prev = &dummy;
    while (head1 && head2) {
        if (head1->m_value < head2->m_value) {
            prev->m_next = head1;
            head1 = head1->m_next;
        } else {
            prev->m_next = head2;
            head2 = head2->m_next;
        }
        prev = prev->m_next;
    }
    if (head1) {
        prev->m_next = head1;
    } else {
        prev->m_next = head2;
    }
    return dummy.m_next;
}
# 面试题 26：树的子结构


# 题目


输入两棵二叉树  A  和  B ，判断  B  是不是  A  的子结构。二叉树节点的定义如下：


struct BinaryTreeNode {
    double m_value;
    BinaryTreeNode *m_left;
    BinaryTreeNode *m_right;
};
# 思路


我们可以分成两步来判断树的子结构是否相同：


    

  1. 在树  A  中找到和树  B  的根节点的值一样的节点  R ；
    2. 

  2. 判断树  A  中以  R  为根节点的子树是不是包含和树  B  一样的结构。
    3. 



上面这个过程可以很明显地写成递归的形式。


# 代码


#include <iostream>
#include <cmath>
using namespace std;
struct BinaryTreeNode {
    double m_value;
    BinaryTreeNode *m_left;
    BinaryTreeNode *m_right;
};
bool equal(double a, double b) {
    return abs(a - b) < 1e-6;
}
bool does_tree_has_subtree(BinaryTreeNode *root, BinaryTreeNode *subtree_root) {
    if (subtree_root == nullptr) {
        return true;
    }
    if (root == nullptr) {
        return false;
    }
    if (equal(root->m_value, subtree_root->m_value) == false) {
        return false;
    }
    return does_tree_has_subtree(root->m_left, subtree_root->m_left) &&
           does_tree_has_subtree(root->m_right, subtree_root->m_right);
}
bool has_subtree(BinaryTreeNode *root_A, BinaryTreeNode *root_B) {
    bool result = false;
    if (root_A != nullptr && root_B  != nullptr) {
        if (equal(root_A->m_value, root_B->m_value)) {
            result = does_tree_has_subtree(root_A, root_B);
        }
        if (result == false) {
            result = has_subtree(root_A->m_left, root_B);
        }
        if (result == false) {
            result = has_subtree(root_B->m_right, root_B);
        }
    }
    return result;
}