内容简介：Java 基础系列 22：有关链表的经典面试题目解析与代码实现
前言：在上一篇的 java 基础系列文章（PS：https://www.zifangsky.cn/933.html）中，我介绍了什么是链表、链表的优缺点以及常见链表结构（如：单向链表、双向链表、循环链表）的定义、遍历、插入、删除等基本操作的代码实现。因此，在这一篇文章中我将进一步介绍如何解析有关链表的常见问题，最后则是给出其Java实现的参考代码
问题1：找到链表的倒数第n个节点
（1）思路分析：
这个问题很简单，我们可以使用多种方法来找到链表的倒数第n个节点。其中几种最常见的实现思路如下：
i） 使用蛮力法 ：从链表的第一个节点开始向后移动，针对每一个节点都统计它后面还有多少个节点。如果节点数小于n-1个，则表示整个链表长度不足n个，返回提示信息“链表中总节点数目不足n个”；如果节点数大于n-1个，则向后移动一个节点，并继续统计该节点后面的节点个数；如果节点数刚好为n-1个，则表示已经找到目标节点，算法结束
时间复杂度：O(n²)。因为针对每个节点都需要扫描一次它之后的所有节点。从时间复杂度可以看出，这种算法是一种效率很差的算法，因此不考虑使用
ii） 使用散列表（哈希表） ：遍历一次链表，在遍历每个节点的时候分别在散列表中存储<节点位置,节点地址>。假设链表长度为M，则目标问题转换成为：求链表中正数第M-n+1个节点，也就是返回散列表中主键为M-n+1的值即可
时间复杂度：O(n)。因为需要遍历一次链表
iii）不使用散列表求解问题。思路类似上面的散列表实现思路，不同的是这次是通过两次遍历链表的操作来实现：第一次遍历链表得到链表的长度M，第二次遍历找到正数第M-n+1个节点
时间复杂度：O(n)。时间开销表现在第一次遍历确认链表长度的时间开销以及从表头开始寻找第M-n+1个节点的时间开销，即：T(n) = O(n) + O(m) ≈ O(n)
iv） 扫描一次链表就解决问题 。定义两个指针都指向链表的表头节点，其中一个节点先移动 n-1 次，然后两个指针同时开始向后移动，当处于前面的指针移动到表尾节点时，则此时处于后面的指针即是我们需要求取的节点
时间复杂度：O(n)
（2）示例代码：
package cn.zifangsky.linkedlist.questions;
import java.util.HashMap;
import java.util.Map;
import org.junit.Test;
import cn.zifangsky.linkedlist.SinglyNode;
/**
* 找到链表的倒数第n个节点
* @author zifangsky
*
*/
public class Question1 {
/**
* 方法一：使用散列表。通过遍历将所有节点存储到散列表中，再从散列表中返回目标节点
*
* @时间复杂度 O(n)
* @param headNode
* @param n
* @return
*/
public SinglyNode Method1(SinglyNode headNode,int n){
Map<Integer,SinglyNode> nodeMap = new HashMap<>();
SinglyNode currentNode = headNode;
for(int i=1;currentNode!=null;i++){
nodeMap.put(i, currentNode);
currentNode = currentNode.getNext();
}
if(n < 1 || n > nodeMap.size()){
throw new RuntimeException("输入参数存在错误");
}else{
return nodeMap.get(nodeMap.size() - n + 1);
}
}
/**
* 方法二：首先遍历获取链表长度，再次遍历得到目标节点
*
* @时间复杂度 T(n)=O(n)+O(n)≈O(n)
* @param headNode
* @param n
* @return
*/
public SinglyNode Method2(SinglyNode headNode,int n){
//1，获取链表长度
int length = 0;
SinglyNode currentNode = headNode;
while(currentNode != null){
length++;
currentNode = currentNode.getNext();
}
if(n < 1 || n > length){
throw new RuntimeException("输入参数存在错误");
}else{//2，再次遍历得到目标节点
currentNode = headNode;
for(int i=1;i<length-n+1;i++){
currentNode = currentNode.getNext();
}
return currentNode;
}
}
/**
* 方法三：定义两个指针，二者相差n-1个节点，然后一起移动直到链表末尾
*
* @时间复杂度 O(n)
* @param headNode
* @param n
* @return
*/
public SinglyNode Method3(SinglyNode headNode,int n){
SinglyNode frontNode=headNode,laterNode=headNode;
//1，frontNode先移动 n-1 次
for(int i=1;i<n;i++){
if(frontNode != null){
frontNode = frontNode.getNext();
}else{
return null;
}
}
//2，frontNode和laterNode一起移动到链表结束
while(frontNode != null && frontNode.getNext() != null){
frontNode = frontNode.getNext();
laterNode = laterNode.getNext();
}
return laterNode;
}
@Test
public void testMethods(){
SinglyNode headNode = new SinglyNode(11);
SinglyNode currentNode = headNode;
for(int i=2;i<=5;i++){
SinglyNode tmpNode = new SinglyNode(11 * i);
currentNode.setNext(tmpNode);
currentNode = tmpNode;
}
//方法一
System.out.println("方法一：" + Method1(headNode, 2));
//方法二
System.out.println("方法二：" + Method2(headNode, 2));
//方法三
System.out.println("方法三：" + Method3(headNode, 2));
}
}
输出如下：
方法一：SinglyNode [data=44] 方法二：SinglyNode [data=44] 方法三：SinglyNode [data=44]
问题2：如何判断给定的链表是以NULL结尾，还是形成了一个环？
（1）思路分析：
i） 蛮力法 ：从表头开始遍历，针对每个节点均检查是否存在它之后的某个节点的后继指针指向该节点，如果存在则说明该链表存在环。如果一直遍历到表尾节点都未发现这种节点，则说明该链表不存在环。很显然这种算法是一种效率很差的算法，因此不考虑使用
ii） 使用散列表（哈希表） ：从表头开始逐个遍历链表中的每个节点，并检查其是否已经存在散列表中。如果存在则说明已经访问过该节点了，也就是存在环；如果一直到表尾都没有出现已经访问过的节点，则说明该链表不存在环
时间复杂度：O(n)
iii） Floyd环判定算法 ：使用两个在链表中具有不同移动速度的指针（如：fastNode每次移动两个节点，slowNode每次移动一个节点），两个指针同时从表头开始移动，如果在某一时刻它们相遇了，则表明该链表存在环。原因很简单：快速移动指针和慢速移动指针将会指向同一位置的唯一可能情况就是整个或者部分链表是一个环
时间复杂度：O(n)
（2）示例代码：
package cn.zifangsky.linkedlist.questions;
import java.util.HashMap;
import java.util.Map;
import org.junit.Test;
import cn.zifangsky.linkedlist.SinglyNode;
/**
* 判断给定的链表是以NULL结尾，还是形成了一个环？
* @author zifangsky
*
*/
public class Question2 {
/**
* 方法一：使用散列表。从表头开始逐个遍历链表中的每个节点，检查其是否已经存在散列表中。
* 如果存在则说明已经访问过该节点了，也就是存在环；如果一直到表尾都没有出现已经访问过的节点，
* 则说明该链表不存在环
*
* @时间复杂度 O(n)
* @param headNode
* @return
*/
public boolean Method1(SinglyNode headNode){
Map<Integer,SinglyNode> nodeMap = new HashMap<>();
SinglyNode currentNode = headNode;
for(int i=1;currentNode!=null;i++){
if(nodeMap.containsValue(currentNode)){
return true;
}else{
nodeMap.put(i, currentNode);
currentNode = currentNode.getNext();
}
}
return false;
}
/**
* Floyd环判定算法：
* 使用两个在链表中具有不同移动速度的指针同时移动，一旦它们进入环就一定会相遇
* 原因：fast指针和slow指针只有当整个或者部分链表是一个环时才会相遇
*
* @时间复杂度 O(n)
* @param headNode
* @return
*/
public boolean Method2(SinglyNode headNode){
SinglyNode fastNode=headNode,slowNode=headNode;
while(slowNode.getNext() != null && fastNode.getNext() != null && fastNode.getNext().getNext() != null){
slowNode = slowNode.getNext();
fastNode = fastNode.getNext().getNext();
if(slowNode == fastNode){
return true;
}
}
return false;
}
@Test
public void testMethods(){
SinglyNode headNode1 = new SinglyNode(11);
SinglyNode currentNode = headNode1;
for(int i=2;i<=5;i++){
SinglyNode tmpNode = new SinglyNode(11 * i);
currentNode.setNext(tmpNode);
currentNode = tmpNode;
}
//链表headNode2，人为构造了一个环
SinglyNode headNode2 = new SinglyNode(11);
SinglyNode ringStartNode = null;
currentNode = headNode2;
for(int i=2;i<=8;i++){
SinglyNode tmpNode = new SinglyNode(11 * i);
currentNode.setNext(tmpNode);
currentNode = tmpNode;
if(i == 3){
ringStartNode = tmpNode;
}else if(i == 8){
tmpNode.setNext(ringStartNode);
}
}
//方法一
System.out.println("方法一：链表headNode1是否存在环：" + Method1(headNode1)
+ "；链表headNode2是否存在环：" + Method1(headNode2));
//方法二
System.out.println("方法二：链表headNode1是否存在环：" + Method2(headNode1)
+ "；链表headNode2是否存在环：" + Method2(headNode2));
}
}
输出如下：
方法一：链表headNode1是否存在环：false；链表headNode2是否存在环：true 方法二：链表headNode1是否存在环：false；链表headNode2是否存在环：true
问题3：如何判断给定的链表是以NULL结尾，还是形成了一个环？如果链表中存在环，则找到环的起始节点
（1）思路分析：
首先使用Floyd环判定算法判断一个链表是否存在环。在找到环之后，将slowNode重新设置为表头节点，接下来slowNode和fastNode每次分别移动一个节点，当它们再次相遇时即为环的起始节点
时间复杂度：O(n)
证明：
设飞环长度为：C1，整个环的长度为：C2，两个指针相遇时走过的环中的弧长为：C3
第一次相遇时：
Sslow = C1 + C3
Sfast = C1 + C2 + C3
且：Sfast = 2Sslow
则：C1 = C2 – C3
当slowNode重置为表头节点，两个指针只需要分别移动C1即可第二次相遇：
slowNode移动长度：C1，此时slowNode的位置是环的开始节点
fastNode移动长度：C1 = C2 – C3，也就是说fastNode此时的位置是：初始位置C3 + C2 – C3 = C2，也就是说fastNode此时刚好移动到环的开始节点，二者相遇
（2）示例代码：
package cn.zifangsky.linkedlist.questions;
import org.junit.Test;
import cn.zifangsky.linkedlist.SinglyNode;
/**
* 判断给定的链表是以NULL结尾，还是形成了一个环？如果链表中存在环，则找到环的起始节点
* @author zifangsky
*
*/
public class Question3 {
/**
* 在找到环之后，将slowNode重新设置为表头节点，接下来slowNode和fastNode每次分别移动一个节点，
* 当它们再次相遇时即为环的起始节点
*
* @时间复杂度 O(n)
* @param headNode
* @return
*/
public SinglyNode findLoopStartNode(SinglyNode headNode){
SinglyNode fastNode=headNode,slowNode=headNode;
boolean loopExists = false; //是否存在环的标识
while(slowNode.getNext() != null && fastNode.getNext() != null && fastNode.getNext().getNext() != null){
slowNode = slowNode.getNext();
fastNode = fastNode.getNext().getNext();
if(slowNode == fastNode){
loopExists = true;
break;
}
}
//如果存在环，则slowNode回到表头
if(loopExists){
slowNode = headNode;
while(slowNode != fastNode){
slowNode = slowNode.getNext();
fastNode = fastNode.getNext();
}
return fastNode;
}
return null;
}
@Test
public void testMethods(){
SinglyNode headNode1 = new SinglyNode(11);
SinglyNode currentNode = headNode1;
for(int i=2;i<=5;i++){
SinglyNode tmpNode = new SinglyNode(11 * i);
currentNode.setNext(tmpNode);
currentNode = tmpNode;
}
//链表headNode2，人为构造了一个环
SinglyNode headNode2 = new SinglyNode(11);
SinglyNode ringStartNode = null;
currentNode = headNode2;
for(int i=2;i<=8;i++){
SinglyNode tmpNode = new SinglyNode(11 * i);
currentNode.setNext(tmpNode);
currentNode = tmpNode;
if(i == 3){
ringStartNode = tmpNode;
}else if(i == 8){
tmpNode.setNext(ringStartNode);
}
}
System.out.println("链表headNode1的环的起始节点：" + findLoopStartNode(headNode1)
+ "；链表headNode2的环的起始节点：" + findLoopStartNode(headNode2));
}
}
输出如下：
链表headNode1的环的起始节点：null；链表headNode2的环的起始节点：SinglyNode [data=33]
问题4：如何判断给定的链表是以NULL结尾，还是形成了一个环？如果链表中存在环，则返回环的长度
（1）思路分析：
首先使用Floyd环判定算法判断一个链表是否存在环。在找到环之后，保持fastNode不动，接下来slowNode每次移动一个节点，同时计数器加一，当它们再次相遇时即可求出环的长度
时间复杂度：O(n)
（2）示例代码：
package cn.zifangsky.linkedlist.questions;
import org.junit.Test;
import cn.zifangsky.linkedlist.SinglyNode;
/**
* 判断给定的链表是以NULL结尾，还是形成了一个环？如果链表中存在环，则返回环的长度
* @author zifangsky
*
*/
public class Question4 {
/**
* 在找到环之后，保持fastNode不动，接下来slowNode每次移动一个节点，同时计数器加一，
* 当它们再次相遇时即可求出环的长度
*
* @时间复杂度 O(n)
* @param headNode
* @return
*/
public int findLoopLength(SinglyNode headNode){
SinglyNode fastNode=headNode,slowNode=headNode;
boolean loopExists = false; //是否存在环的标识
int length = 0; //环的长度
while(slowNode.getNext() != null && fastNode.getNext() != null && fastNode.getNext().getNext() != null){
slowNode = slowNode.getNext();
fastNode = fastNode.getNext().getNext();
if(slowNode == fastNode){
loopExists = true;
break;
}
}
//如果存在环，则保持fastNode不动，slowNode逐个移动，直到二者再次相遇
if(loopExists){
slowNode = slowNode.getNext();
length++;
while(slowNode != fastNode){
slowNode = slowNode.getNext();
length++;
}
}
return length;
}
@Test
public void testMethods(){
SinglyNode headNode1 = new SinglyNode(11);
SinglyNode currentNode = headNode1;
for(int i=2;i<=5;i++){
SinglyNode tmpNode = new SinglyNode(11 * i);
currentNode.setNext(tmpNode);
currentNode = tmpNode;
}
//链表headNode2，人为构造了一个环
SinglyNode headNode2 = new SinglyNode(11);
SinglyNode ringStartNode = null;
currentNode = headNode2;
for(int i=2;i<=8;i++){
SinglyNode tmpNode = new SinglyNode(11 * i);
currentNode.setNext(tmpNode);
currentNode = tmpNode;
if(i == 3){
ringStartNode = tmpNode;
}else if(i == 8){
tmpNode.setNext(ringStartNode);
}
}
System.out.println("链表headNode1的环的长度：" + findLoopLength(headNode1)
+ "；链表headNode2的环的长度：" + findLoopLength(headNode2));
}
}
输出如下：
链表headNode1的环的长度：0；链表headNode2的环的长度：6
问题5：向有序链表中插入一个节点
（1）思路分析：
遍历链表，找到存放元素的正确位置之后，插入节点
时间复杂度：O(n)
（2）示例代码：
package cn.zifangsky.linkedlist.questions;
import org.junit.Test;
import cn.zifangsky.linkedlist.SinglyNode;
import cn.zifangsky.linkedlist.SinglyNodeOperations;
/**
* 向有序链表中插入一个节点
* @author zifangsky
*
*/
public class Question5 {
/**
* 向有序链表中插入一个节点
*
* @时间复杂度 O(n)
* @param headNode
* @param newNode
* @return
*/
public SinglyNode insertIntoSortedList(SinglyNode headNode,SinglyNode newNode){
if(newNode.getData() <= headNode.getData()){
newNode.setNext(headNode);
return newNode;
}else{
SinglyNode currentNode=headNode;
while(currentNode.getNext() != null && newNode.getData() > currentNode.getNext().getData()){
currentNode = currentNode.getNext();
}
newNode.setNext(currentNode.getNext());
currentNode.setNext(newNode);
return headNode;
}
}
@Test
public void testMethods(){
SinglyNode headNode = new SinglyNode(11);
SinglyNode currentNode = headNode;
for(int i=2;i<=5;i++){
SinglyNode tmpNode = new SinglyNode(11 * i);
currentNode.setNext(tmpNode);
currentNode = tmpNode;
}
//遍历初始链接
SinglyNodeOperations.print(headNode);
SinglyNode newNode = new SinglyNode(66);
headNode = insertIntoSortedList(headNode, newNode);
//遍历最终结果
SinglyNodeOperations.print(headNode);
}
}
输出如下：
问题6：如何逆置单向链表？
（1）思路分析：
略
时间复杂度：O(n)
（2）示例代码：
package cn.zifangsky.linkedlist.questions;
import org.junit.Test;
import cn.zifangsky.linkedlist.SinglyNode;
import cn.zifangsky.linkedlist.SinglyNodeOperations;
/**
* 如何逆置单向链表？
* @author zifangsky
*
*/
public class Question6 {
/**
* @时间复杂度 O(n)
* @param headNode
* @return
*/
public SinglyNode ReverseList(SinglyNode headNode){
SinglyNode tempNode=null,nextNode=null;
while(headNode != null){
nextNode = headNode.getNext();
headNode.setNext(tempNode);
tempNode = headNode;
headNode = nextNode;
}
return tempNode;
}
@Test
public void testMethods(){
SinglyNode headNode = new SinglyNode(11);
SinglyNode currentNode = headNode;
for(int i=2;i<=5;i++){
SinglyNode tmpNode = new SinglyNode(11 * i);
currentNode.setNext(tmpNode);
currentNode = tmpNode;
}
//遍历初始链表
SinglyNodeOperations.print(headNode);
headNode = ReverseList(headNode);
//遍历最终结果
SinglyNodeOperations.print(headNode);
}
}
输出如下：
问题7：如何逐对逆置单向链表？
如果初始节点链表是：11 –> 22 –> 33 –> 44 –> 55 –> 66 –> 77，那么经过逐对逆置后，新链表变成：22 –> 11 –> 44 –> 33 –> 66 55 –> 77
（1）思路分析：
略
时间复杂度：O(n)
（2）示例代码：
package cn.zifangsky.linkedlist.questions;
import org.junit.Test;
import cn.zifangsky.linkedlist.SinglyNode;
import cn.zifangsky.linkedlist.SinglyNodeOperations;
/**
* 如何逐对逆置单向链表？
* @author zifangsky
*
*/
public class Question7 {
/**
* @时间复杂度 O(n)
* @param headNode
* @return
*/
public SinglyNode ReverseList(SinglyNode headNode){
SinglyNode tempNode=null;
if(headNode == null || headNode.getNext() == null){
return headNode;
}else{
tempNode = headNode.getNext();
headNode.setNext(tempNode.getNext());
tempNode.setNext(headNode);
tempNode.getNext().setNext(ReverseList(headNode.getNext()));
return tempNode;
}
}
@Test
public void testMethods(){
SinglyNode headNode = new SinglyNode(11);
SinglyNode currentNode = headNode;
for(int i=2;i<=7;i++){
SinglyNode tmpNode = new SinglyNode(11 * i);
currentNode.setNext(tmpNode);
currentNode = tmpNode;
}
//遍历初始链表
SinglyNodeOperations.print(headNode);
headNode = ReverseList(headNode);
//遍历最终结果
SinglyNodeOperations.print(headNode);
}
}
输出如下：
问题8：如何从表尾开始输出链表？
（1）思路分析：
使用递归即可实现从表尾开始输出链表
时间复杂度：O(n)
（2）示例代码：
package cn.zifangsky.linkedlist.questions;
import org.junit.Test;
import cn.zifangsky.linkedlist.SinglyNode;
import cn.zifangsky.linkedlist.SinglyNodeOperations;
/**
* 如何从表尾开始输出链表？
* @author zifangsky
*
*/
public class Question8 {
/**
* 思路：递归，从链表末尾开始输出
* @时间复杂度 O(n)
* @param headNode
* @return
*/
public void printFromEnd(SinglyNode headNode){
if(headNode != null && headNode.getNext() != null){
printFromEnd(headNode.getNext());
}
System.out.print(headNode.getData() + " ");
}
@Test
public void testMethods(){
SinglyNode headNode = new SinglyNode(11);
SinglyNode currentNode = headNode;
for(int i=2;i<=5;i++){
SinglyNode tmpNode = new SinglyNode(11 * i);
currentNode.setNext(tmpNode);
currentNode = tmpNode;
}
//遍历初始链表
SinglyNodeOperations.print(headNode);
//从末尾开始遍历链表
printFromEnd(headNode);
}
}
输出如下：
问题9：判断一个链表的长度是奇数还是偶数？
（1）思路分析：
定义一个在链表中每次移动两个节点的指针。如果最后指针指向NULL，则说明此链表的长度是偶数；如果最后指针指向表尾节点，则说明此链表的长度是奇数
时间复杂度：O(n)
（2）示例代码：
package cn.zifangsky.linkedlist.questions;
import org.junit.Test;
import cn.zifangsky.linkedlist.SinglyNode;
/**
* 判断一个链表的长度是奇数还是偶数？
* @author zifangsky
*
*/
public class Question9 {
/**
* 思路：定义一个在链表中每次移动两个节点的指针，如果最后指针指向NULL，
* 则说明此链表的长度是偶数
* @时间复杂度 O(n)
* @param headNode
* @return
*/
public void CheckList(SinglyNode headNode){
while(headNode != null && headNode.getNext() != null){
headNode = headNode.getNext().getNext();
}
if(headNode == null){
System.out.println("此链表长度为偶数");
}else{
System.out.println("此链表长度为奇数");
}
}
@Test
public void testMethods(){
SinglyNode headNode = new SinglyNode(11);
SinglyNode currentNode = headNode;
for(int i=2;i<=5;i++){
SinglyNode tmpNode = new SinglyNode(11 * i);
currentNode.setNext(tmpNode);
currentNode = tmpNode;
}
CheckList(headNode);
}
}
输出如下：
此链表长度为奇数
问题10：如何将两个有序链表合并成一个新的有序链表？
（1）思路分析：
使用递归依次找出每个位置上的最小的节点
时间复杂度：O(n)
（2）示例代码：
package cn.zifangsky.linkedlist.questions;
import org.junit.Test;
import cn.zifangsky.linkedlist.SinglyNode;
import cn.zifangsky.linkedlist.SinglyNodeOperations;
/**
* 如何将两个有序链表合并成一个新的有序链表？
* @author zifangsky
*
*/
public class Question10 {
/**
* 思路：递归依次比较大小
* @时间复杂度 O(n/2) = O(n)
* @param headNode
* @return
*/
public SinglyNode MergeList(SinglyNode headNode1,SinglyNode headNode2){
SinglyNode result = null;
if(headNode1 == null) return headNode2;
if(headNode2 == null) return headNode1;
if(headNode1.getData() <= headNode2.getData()){
result = headNode1;
result.setNext(MergeList(headNode1.getNext(),headNode2));
}else{
result = headNode2;
result.setNext(MergeList(headNode1, headNode2.getNext()));
}
return result;
}
@Test
public void testMethods(){
SinglyNode a = new SinglyNode(11);
SinglyNode b = new SinglyNode(22);
SinglyNode currentA = a,currentB = b;
for(int i=3;i<=8;i++){
SinglyNode tmpNode = new SinglyNode(11 * i);
if(i%2 == 0){
currentB.setNext(tmpNode);
currentB = tmpNode;
}else{
currentA.setNext(tmpNode);
currentA = tmpNode;
}
}
//遍历初始链表
System.out.print("A: ");
SinglyNodeOperations.print(a);
System.out.print("B: ");
SinglyNodeOperations.print(b);
System.out.print("合并之后: ");
SinglyNodeOperations.print(MergeList(a, b));
}
}
输出如下：
A: 11 33 55 77 B: 22 44 66 88 合并之后: 11 22 33 44 55 66 77 88
问题11：如何找到链表的中间节点？
（1）思路分析：
i）遍历两次：第一次遍历得到链表的长度N，第二次遍历定位到 N/2 个节点，即为中间节点
ii）使用散列表：略
iii）分别定义两个移动速度为：1节点/次、2节点/次的指针，当速度较快的指针移动到链表末尾时，此时速度较慢的指针指向的节点即为中间节点
时间复杂度：O(n)
（2）示例代码：
package cn.zifangsky.linkedlist.questions;
import org.junit.Test;
import cn.zifangsky.linkedlist.SinglyNode;
import cn.zifangsky.linkedlist.SinglyNodeOperations;
/**
* 如何找到链表的中间节点？
* @author zifangsky
*
*/
public class Question11 {
/**
* 思路：分别定义两个移动速度为：1节点/次、2节点/次的指针，
* 当速度较快的指针移动到链表末尾时，此时速度较慢的指针指向的节点即为中间节点
* @时间复杂度 O(n/2) = O(n)
* @param headNode
* @return
*/
public SinglyNode findMiddle(SinglyNode headNode){
if(headNode != null){
SinglyNode slow = headNode,fast = headNode;
while(fast != null && fast.getNext() != null && fast.getNext().getNext() != null){
slow = slow.getNext();
fast = fast.getNext().getNext();
}
return slow;
}else{
return null;
}
}
@Test
public void testMethods(){
SinglyNode headNode = new SinglyNode(11);
SinglyNode currentNode = headNode;
for(int i=2;i<=6;i++){
SinglyNode tmpNode = new SinglyNode(11 * i);
currentNode.setNext(tmpNode);
currentNode = tmpNode;
}
//遍历初始链接
SinglyNodeOperations.print(headNode);
System.out.println("链表中间节点是： " + findMiddle(headNode));
}
}
输出如下：
11 22 33 44 55 66 链表中间节点是： SinglyNode [data=33]
问题12：假设两个单向链表在某个节点相交后，成为一个单向链表，求该交点？
（1）思路分析：
i） 使用蛮力法 ：遍历第一个链表，将第一个链表中的每个节点都和第二个链表中的每个节点比较，如果出现相等的节点时，即为相交节点
时间复杂度：O(mn)
ii） 使用散列表 ：遍历第一个链表，将第一个链表中的每个节点都存入散列表中。再次遍历第二个链表，对于第二个链表中的每个节点均检查是否已经存在于散列表中，如果存在则说明该节点为交点
时间复杂度：O(m) + O(n) = O(max(m,n))
iii） 使用栈求解 ：定义两个栈分别存储两个链表。分别遍历两个链表并压入到对应的栈中。比较两个栈的栈顶元素，如果二者相等则将该栈顶元素存储到临时变量中，并弹出两个栈的栈顶元素。重复上述操作一直到两个栈的栈顶元素不相等为止。最后存储的的临时变量即为交点
时间复杂度：O(m) + O(n) = O(max(m,n))
iv）分别获得两个链表的长度，计算出两个链表的长度差d，较长的链表首先移动d步，然后两个链表同时向表尾移动，当出现两个节点相同时即为交点
时间复杂度：O(m) + O(n) = O(max(m,n))
（2）示例代码：
package cn.zifangsky.linkedlist.questions;
import java.util.HashMap;
import java.util.Map;
import org.junit.Test;
import cn.zifangsky.linkedlist.SinglyNode;
import cn.zifangsky.linkedlist.SinglyNodeOperations;
/**
* 找出两个相交链表的交点
* @author zifangsky
*
*/
public class Question12 {
/**
* 思路：使用散列表求解
* @时间复杂度 O(m) + O(n) = O(max(m,n))，即：O(m)或O(n)
* @param headNode
* @return
*/
public SinglyNode findIntersection1(SinglyNode headNode1,SinglyNode headNode2){
Map<Integer,SinglyNode> nodeMap = new HashMap<>();
for(int i=1;headNode1!=null;i++){
nodeMap.put(i, headNode1);
headNode1 = headNode1.getNext();
}
while (headNode2 != null) {
if(nodeMap.containsValue(headNode2)){
return headNode2;
}else{
headNode2 = headNode2.getNext();
}
}
return null;
}
/**
* 思路：1，分别获得两个链表的长度；2，计算出两个链表的长度差d；
* 3，较长的链表首先移动d步，然后两个链表同时向表尾移动
* 4，当出现两个节点相同时即为交点
* @时间复杂度 O(m) + O(n) + O(1) + O(d) + O(min(m,n)) = O(max(m,n))
* @param headNode1
* @param headNode2
* @return
*/
public SinglyNode findIntersection2(SinglyNode headNode1,SinglyNode headNode2){
int length1 = 0,length2 = 0; //两个链表节点数
int diff = 0;
SinglyNode temp1 = headNode1,temp2 = headNode2;
//1
while (temp1 != null) {
length1++;
temp1 = temp1.getNext();
}
while (temp2 != null) {
length2++;
temp2 = temp2.getNext();
}
//2、3
if(length1 > 0 && length2 > 0 && length2 >= length1){
diff = length2 - length1;
for(int i=1;i<=diff;i++){
headNode2 = headNode2.getNext();
}
}else if(length1 > 0 && length2 > 0 && length2 < length1){
diff = length1 - length2;
for(int i=1;i<=diff;i++){
headNode1 = headNode1.getNext();
}
}else{
return null;
}
//4
while(headNode1 != null && headNode2 != null){
if(headNode1 == headNode2){
return headNode1;
}else{
headNode1 = headNode1.getNext();
headNode2 = headNode2.getNext();
}
}
return null;
}
@Test
public void testMethods(){
//人为构造两个相交的链表
SinglyNode a = new SinglyNode(11);
SinglyNode b = new SinglyNode(22);
SinglyNode currentA = a,currentB = b;
for(int i=3;i<=8;i++){
SinglyNode tmpNode = new SinglyNode(11 * i);
if(i < 7){
if(i%2 == 0){
currentB.setNext(tmpNode);
currentB = tmpNode;
SinglyNode tmpNode2 = new SinglyNode(11 * i + 1);
currentB.setNext(tmpNode2);
currentB = tmpNode2;
}else{
currentA.setNext(tmpNode);
currentA = tmpNode;
}
}else{
currentB.setNext(tmpNode);
currentB = tmpNode;
currentA.setNext(tmpNode);
currentA = tmpNode;
}
}
//遍历初始链表
System.out.print("A: ");
SinglyNodeOperations.print(a);
System.out.print("B: ");
SinglyNodeOperations.print(b);
System.out.println("方法一，其交点是: " + findIntersection1(a,b));
System.out.println("方法二，其交点是: " + findIntersection2(a,b));
}
}
输出如下：
A: 11 33 55 77 88 B: 22 44 45 66 67 77 88 方法一，其交点是: SinglyNode [data=77] 方法二，其交点是: SinglyNode [data=77]
问题13：如何把一个循环链表分割成两个长度相等的部分？如果链表的节点数是奇数，那么让第一个链表的节点数比第二个链表多一个
（1）思路分析：
定义两个移动速度不一样的指针：fastNode每次移动两个节点，slowNode每次移动一个节点。当slowNode移动到中间节点的时候，如果链表有奇数个节点，此时fastNode.getNext()指向headNode；如果链表有偶数个节点，此时fastNode.getNext().getNext()指向headNode
时间复杂度：O(n)
（2）示例代码：
package cn.zifangsky.linkedlist.questions;
import org.junit.Test;
import cn.zifangsky.linkedlist.CircularNode;
import cn.zifangsky.linkedlist.CircularNodeOperations;
/**
* 如何把一个循环链表分割成两个长度相等的部分？
* @author zifangsky
*
*/
public class Question13 {
/**
* 思路：
* 定义两个移动速度不一样的指针：fastNode每次移动两个节点，slowNode每次移动一个节点。
* 当slowNode移动到中间节点的时候，如果链表有奇数个节点，此时fastNode.getNext()指向headNode；
* 如果链表有偶数个节点，此时fastNode.getNext().getNext()指向headNode
* @时间复杂度 O(n)
* @param headNode
*/
public void splitList(CircularNode headNode){
if(headNode == null)
return;
CircularNode fastNode = headNode,slowNode = headNode;
while(fastNode.getNext() != headNode && fastNode.getNext().getNext() != headNode){
fastNode = fastNode.getNext().getNext();
slowNode = slowNode.getNext();
}
CircularNode result1 = null,result2 = null; //定义两个分割之后的子链表
result1 = headNode; //设置前半部分的head指针
if(headNode.getNext() != headNode){
result2 = slowNode.getNext(); //设置后半部分的head指针
}
//如果链表有偶数个节点，此时fastNode再向后移动一个节点
if(fastNode.getNext().getNext() == headNode){
fastNode = fastNode.getNext();
}
fastNode.setNext(slowNode.getNext()); //把后半部分闭合成环
slowNode.setNext(headNode); //把前半部分闭合成环
//测试输出两个子链表
System.out.print("子链表1：");
CircularNodeOperations.print(result1);
System.out.print("子链表2：");
if(result2 != null){
CircularNodeOperations.print(result2);
}
}
@Test
public void testMethods(){
CircularNode headNode = new CircularNode(11);
CircularNode currentNode = headNode;
for(int i=2;i<=7;i++){
CircularNode tmpNode = new CircularNode(11 * i);
currentNode.setNext(tmpNode);
currentNode = tmpNode;
if(i == 7){
currentNode.setNext(headNode);
}
}
//遍历初始链接
CircularNodeOperations.print(headNode);
splitList(headNode);
}
}
输出如下：
11 22 33 44 55 66 77 子链表1：11 22 33 44 子链表2：55 66 77
问题14：约瑟夫环：N个人想选出一个领头人。他们排成一个环，沿着环每次数到第M个人就从环中排出该人，并从下一个人开始继续数。请找出最后留在环中的人
（1）思路分析：
略
时间复杂度：O(n)
（2）示例代码：
package cn.zifangsky.linkedlist.questions;
import org.junit.Test;
import cn.zifangsky.linkedlist.CircularNode;
/**
* 约瑟夫环问题
* @author zifangsky
*
*/
public class Question14 {
/**
*
* @param N 人数
* @param M 每次数数个数
*/
public void getLastPerson(int N,int M){
//构建一个环
CircularNode headNode = new CircularNode(1);
CircularNode currentNode = headNode;
for(int i=2;i<=N;i++){
CircularNode tmpNode = new CircularNode(i);
currentNode.setNext(tmpNode);
currentNode = tmpNode;
if(i == N){
currentNode.setNext(headNode);
}
}
//当链表大于一个节点时一直循环排除下去
while(headNode.getNext() != headNode){
for(int i=1;i<M;i++){
headNode = headNode.getNext();
}
headNode.setNext(headNode.getNext().getNext()); //排除headNode.getNext()这个人
}
System.out.println("剩下的人是： " + headNode.getData());
}
@Test
public void testMethods(){
getLastPerson(5,3);
}
}
输出如下：
剩下的人是： 5
问题15：给定一个单向链表，要求从链表表头开始找到最后一个满足 i%k==0 的节点
例如：n为7，k为3，那么应该返回第6个节点
（1）思路分析：
略
时间复杂度：O(n)
（2）示例代码：
package cn.zifangsky.linkedlist.questions;
import org.junit.Test;
import cn.zifangsky.linkedlist.SinglyNode;
import cn.zifangsky.linkedlist.SinglyNodeOperations;
/**
* 寻找模节点，即：从链表表头开始找到最后一个满足 i%k==0 的节点
* @author zifangsky
*
*/
public class Question15 {
/**
* 思路：略
* @时间复杂度 O(n)
* @param headNode
* @param k
* @return
*/
public SinglyNode getModularNode(SinglyNode headNode,int k){
SinglyNode result = null;
if(k <= 0){
return null;
}
for(int i=1;headNode!=null;i++){
if(i % k == 0){
result = headNode;
}
headNode = headNode.getNext();
}
return result;
}
@Test
public void testMethods(){
SinglyNode headNode = new SinglyNode(1);
SinglyNode currentNode = headNode;
for(int i=2;i<=7;i++){
SinglyNode tmpNode = new SinglyNode(i);
currentNode.setNext(tmpNode);
currentNode = tmpNode;
}
//遍历初始链接
SinglyNodeOperations.print(headNode);
System.out.println("目标节点是： " + getModularNode(headNode,3));
}
}
输出如下：
1 2 3 4 5 6 7 目标节点是： SinglyNode [data=6]
问题16：给定一个单向链表，要求从链表表尾开始找到第一个满足 i%k==0 的节点
例如：n为7，k为3，那么应该返回第5个节点
（1）思路分析：
略
时间复杂度：O(n)
（2）示例代码：
package cn.zifangsky.linkedlist.questions;
import org.junit.Test;
import cn.zifangsky.linkedlist.SinglyNode;
import cn.zifangsky.linkedlist.SinglyNodeOperations;
/**
* 从表尾开始寻找模节点，即：从链表表尾开始找到第一个满足 i%k==0 的节点
* @author zifangsky
*
*/
public class Question16 {
/**
* 思路：
* headNode首先移动k个节点，然后headNode和result再分别逐步向表尾移动，
* 当headNode移动到NULL时，此时result即为目标节点
* @时间复杂度 O(n)
* @param headNode
* @param k
* @return
*/
public SinglyNode getModularNode(SinglyNode headNode,int k){
SinglyNode result = headNode;
if(k <= 0){
return null;
}
for(int i=1;i<=k;i++){
if(headNode != null){
headNode = headNode.getNext();
}else{
return null;
}
}
while (headNode != null) {
result = result.getNext();
headNode = headNode.getNext();
}
return result;
}
@Test
public void testMethods(){
SinglyNode headNode = new SinglyNode(1);
SinglyNode currentNode = headNode;
for(int i=2;i<=7;i++){
SinglyNode tmpNode = new SinglyNode(i);
currentNode.setNext(tmpNode);
currentNode = tmpNode;
}
//遍历初始链接
SinglyNodeOperations.print(headNode);
System.out.println("目标节点是： " + getModularNode(headNode,3));
}
}
输出如下：
1 2 3 4 5 6 7 目标节点是： SinglyNode [data=5]
好了，有关链表的经典面试题目解析到这里就结束了。希望我这里的抛砖引玉可以对正在复习这一块内容的同学有所帮助，同时也希望可以进一步加深大家对链表的理解，举一反三，能够更灵活地使用链表这种数据结构
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
猜你喜欢:
- 关于 Kafka 的一些面试题目
- 面试题目：反转链表的算法实现
- Go 面试必考题目之 method 篇
- Go面试必考题目之slice篇
- Redis不懂，面试担心不过，一次性解决面试Redis题目（含答案）？
- 互联网公司面试必问的Redis题目
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
