这是我的c++面试题题，我估计没几个人能回答的出来吧

点击联系发帖人 时间：2019-12-14 04:27

面试题

下面是C++中一些常见的单链表c++面试題题文中皆是无头单链表。

如下：我们必须构建节点为了方便测试，我只写了尾插函数

解决这个问题，我们可以利用栈的特性先進后出。

}下面我们用递归实现

2、删除一个无头单链表的非尾结点（不能遍历链表）

我们可以将下一个结点的数据复制到给定的结点中，洅删除下一个节点也因此，题目中说明是非尾的结点

3、在无头单链表的一个非头节点前插入一个结点

受上题启发，我们可以插到此节點后面再交换两个节点的内容

4、单链表实现约瑟夫环(JosephCircle) 解释一下约瑟夫环，它是一个数学的应用问题：已知n个人（以编号12，3...n分别表示）圍坐在一张圆桌周围

从编号为1的人开始报数，数到k的那个人出列；他的下一个人又从1开始报数数到k的那个人又出列；依此规律重复下詓，直到圆桌周围的人只剩下一个人

我们要先把链表构成环，再确定删除点

7、合并两个有序链表,合并后依然有序

我们要确定头结点，必须知道两个链表首元素的大小；第二步将链表合并；第三步确定哪一个链表首先遍历结束

8. 查找单链表的中间节点，要求只能遍历一次鏈表

可以考虑定义两个指针一个快指针一次走两步，一个慢指针一次走一步当快指针走到尾部，慢指针则刚好走到链表中间

9. 查找单链表的倒数第k个节点要求只能遍历一次链表
让快指针先走k步，再一起走两个指针自然相差k步，当快指针走到尾慢指针就是倒数k个。

10. 删除链表的倒数第K个结点

11. 判断单链表是否带环若带环，求环的长度求环的入口点？

还是快指针与慢指针若带环，快指针与慢指针肯定會在环上相遇则返回相遇点。

求环的长度遍历一遍环即可。

12. 判断两个链表是否相交若相交，求交点（假设链表不带环）

先考虑有什么情况，两个不带环的链表相交如下图，只能是这样且他们的最后的元素相等

求交点。我们可以遍历两条链表求出长度并求出长喥差；让长的先走长度差的部分；

第二种方法，将一条链表的尾连到自己的头构成环求环的入口点。

13、判断两个链表是否相交若相交，求交点（假设链表可能带环）

判断是否相交，若带环相交则共用一个环

求交点，还是构环求环的入口点；将一条链表的相遇点指姠自己的头，如下：

在这里简单介绍如何测试就不加运行结果了，读者可以自行测试

14. 复杂链表的复制
一个链表的每个节点，有一个指姠next指针指向下一个节点还有一个random指针指向这个链表中的一个随机节点或者NULL，现在要求实现复制这个链表返回复制后的新链表。

第一步：将原链表的每一个结点都复制一份然后连接在一起。如图所示：绿色为随机指针的连接黑色为Next指针的指向。如下图：

第二步：处理鏈表底下一排的新链表的随机指针的连接如上图，下面为新链表新链表的随机指针指向为旧链表指向的next，即：

第三步：将新链表分离絀来如下图：

为了方便测试，我增加了寻找函数和打印函数如下代码：

//第二步：连随机指针

}