数据结构4 链表的面试题
这篇文章包含的链表面试题如下：
1、从尾到头打印单向链表
2、查找单向链表中的倒数第k个节点
3、反转一个单向链表【出现频率较高】
4、合并两个有序的单向链表，合并之后的链表依然有序【出现频率较高】
5、找出两个单向链表相交的第一个公共节点
前期代码准备：
下面这两个类的详细解析可以参考我的上一篇文章：数据结构3 线性表之链表
节点类：Node.java
/** * 节点类 */ public class Node { Object element; // 数据域 Node next; // 地址域 // 节点的构造方法 public Node(Object element, Node next) { this.element = element; this.next = next; } // Gettet and Setter public Node getNext() { return this.next; } public void setNext(Node next) { this.next = next; } public Object getElement() { return this.element; } public void setElement(Object element) { this.element = element; } }
链表类：MyLinkedList.java
/** * 自己定义的一个链表类 */ public class MyLinkedList { // 头节点 private Node headNode; // 用来遍历链表的临时节点 private Node tempNode; // Getter public Node getHeadNode() { return headNode; } // Setter public void setHeadNode(Node headNode) { this.headNode = headNode; } // 链表的初始化方法 public MyLinkedList() { // 初始化时，链表里面只有1个节点，所以这个节点的地址域为null Node node = new Node("王重阳", null); // 头节点不存储数据，它的数据域为null，它的地址域存储了第1个节点的地址 headNode = new Node(null, node); } /** * 1、插入节点：时间复杂度为O(n) * @param newNode 需要插入的新节点 * @param position 这个变量的范围可以从0到链表的长度，注意不要越界。 * 头节点不算进链表的长度， * 所以从头节点后面的节点开始算起，position为0 */ public void insert(Node newNode, int position) { // 通过position变量，让tempNode节点从头节点开始遍历，移动到要插入位置的前一个位置 tempNode = headNode; int i = 0; while (i < position) { tempNode = tempNode.next; i++; } newNode.next = tempNode.next; tempNode.next = newNode; } /** * 2、删除节点：时间复杂度为O(n) * @param position */ public void delete(int position) { // 这里同样需要用tempNode从头开始向后查找position tempNode = headNode; int i = 0; while (i < position) { tempNode = tempNode.next; i++; } tempNode.next = tempNode.next.next; } /** * 3、查找节点：时间复杂度为O(n) * @param position * @return 返回查找的节点 */ public Node find(int position) { // 这里同样需要用tempNode从头开始向后查找position tempNode = headNode; int i = 0; while (i < position) { tempNode = tempNode.next; i++; } return tempNode.next; } /** * 4、获取链表的长度：时间复杂度为O(n) * @return */ public int size() { tempNode = headNode.next; int size = 0; while (tempNode.next != null) { size = size + 1; tempNode = tempNode.next; } size = size + 1; // tempNode的地址域为null时，size记得加上最后一个节点 return size; } // 遍历链表，打印出所有节点的方法 public void showAll() { tempNode = headNode.next; while (tempNode.next != null) { System.out.println(tempNode.element); tempNode = tempNode.next; } System.out.println(tempNode.element); } }
1、从尾到头打印单向链表
对于这种颠倒顺序打印的问题，我们应该就会想到栈，后进先出。因此这一题要么自己新建一个栈，要么使用系统的栈（系统递归调用方法时的栈）。需要把链表遍历完一次，所以它的时间复杂度为 O(n)
注意：不能先把链表反转，再遍历输出，因为这样做会破坏链表节点原来的顺序。
方法1：自己新建一个栈
QuestionOneDemo.java
import org.junit.Test; import java.util.Stack; public class QuestionOneDemo { /** * 从尾到头打印单向链表 * 方法1：自己新建一个栈 * * @param head 参数为链表的头节点 */ public void reversePrint(Node head) { // 判断链表是否为空 if (head == null) { return; } // 新建一个栈 Stack<Node> stack = new Stack<Node>(); // 用来遍历的临时节点，从头节点开始 Node tempNode = head; // 从头节点开始遍历链表，将除了头节点之外的所有节点压栈 while (tempNode.getNext() != null) { tempNode = tempNode.getNext(); stack.push(tempNode); } // 将栈中的节点打印输出即可 while (stack.size() > 0) { // 出栈操作 Node node = stack.pop(); System.out.println(node.getElement()); } } /** * 用来测试的方法 */ @Test public void test() { MyLinkedList myLinkedList = new MyLinkedList(); Node newNode1 = new Node("欧阳锋", null); Node newNode2 = new Node("黄药师", null); Node newNode3 = new Node("洪七公", null); myLinkedList.insert(newNode1, 1); myLinkedList.insert(newNode2, 2); myLinkedList.insert(newNode3, 3); System.out.println("----原链表 start----"); myLinkedList.showAll(); System.out.println("----原链表 end----"); System.out.println(""); System.out.println("====从尾到头打印链表 start===="); reversePrint(myLinkedList.getHeadNode()); System.out.println("====从尾到头打印链表 end===="); System.out.println(""); System.out.println("----原链表(依然保留了原来的顺序) start----"); myLinkedList.showAll(); System.out.println("----原链表(依然保留了原来的顺序) end----"); } }
测试结果：
方法2：使用系统的栈（递归）
在 QuestionOneDemo.java 中添加方法2
/** * 从尾到头打印单向链表 * 方法2：自己新建一个栈 * * @param head 参数为链表的头节点 */ public void reversePrint2(Node head) { // 判断传进来的参数节点是否为空 if (head == null) { return; } // 递归 reversePrint2(head.next); System.out.println(head.getElement()); }
测试的方法和测试结果跟方法1一样，这里不再详细列出。
总结：
方法2是基于递归实现的，代码看起来更简洁，但有一个问题：当链表很长的时候，就会导致方法调用的层级很深，有可能造成栈溢出。而方法1是自己新建一个栈，使用循环压栈和循环出栈，代码的稳健性要更好一些。
2、查找单向链表中的倒数第k个节点
2-1：普通思路
先将整个链表从头到尾遍历一次，计算出链表的长度size，得到链表的长度之后，就好办了，直接输出第 size-k 个节点就可以了（注意链表为空，k为0，k大于链表中节点个数的情况）。因为需要遍历两次链表，所以时间复杂度为 T(2n) = O(n)
代码如下：
QuestionTwoDemo.java
import org.junit.Test; public class QuestionTwoDemo { /** * 查找链表中的倒数第k个节点的方法 * * @param myLinkedList 需要查找的链表作为参数传递进来 * @param k 代表倒数第k个节点的位置 * @return */ public Node reciprocalFindNode(MyLinkedList myLinkedList, int k) throws Exception { int size = 0; // 如果头节点为null，说明链表为空 if (myLinkedList.getHeadNode() == null) { throw new Exception("链表为空"); } // 判断k，k不能为0 if (k == 0) { throw new Exception("k不能为0"); } // 第一次遍历，计算出链表的长度size Node tempNode = myLinkedList.getHeadNode(); while (tempNode != null) { size++; tempNode = tempNode.getNext(); } // 判断k，k不能大于链表中节点的个数 if (k > size) { throw new Exception("k不能大于链表中节点的个数"); } // 第二次遍历，找出倒数第k个节点 tempNode = myLinkedList.getHeadNode(); for (int i = 0; i < size - k; i++) { tempNode = tempNode.getNext(); } return tempNode; } /** * 用来测试的方法 */ @Test public void test() throws Exception { MyLinkedList myLinkedList = new MyLinkedList(); Node newNode1 = new Node("欧阳锋", null); Node newNode2 = new Node("黄药师", null); Node newNode3 = new Node("洪七公", null); myLinkedList.insert(newNode1, 1); myLinkedList.insert(newNode2, 2); myLinkedList.insert(newNode3, 3); System.out.println("-----完整的链表start-----"); myLinkedList.showAll(); System.out.println("-----完整的链表end-------"); System.out.println(""); Node node = reciprocalFindNode(myLinkedList, 1); System.out.println("链表的倒数第1个节点是：" + node.getElement()); node = reciprocalFindNode(myLinkedList, 2); System.out.println("链表的倒数第2个节点是：" + node.getElement()); node = reciprocalFindNode(myLinkedList, 3); System.out.println("链表的倒数第3个节点是：" + node.getElement()); node = reciprocalFindNode(myLinkedList, 4); System.out.println("链表的倒数第4个节点是：" + node.getElement()); } }
测试结果：
如果面试官不允许你遍历链表的长度，该怎么做？接下来的改进思路就是。
2-2：改进思路
这里需要用到两个节点型的变量：即变量 first 和 second，首先让 first 和 second 都指向第一个节点，然后让 second 节点往后挪 k-1 个位置，此时 first 和 second 就间隔了 k-1 个位置，然后整体向后移动这两个节点，直到 second 节点走到最后一个节点时，此时 first 节点所指向的位置就是倒数第k个节点的位置。时间复杂度为O(n)
步骤一：
步骤二：
步骤三：
代码：
在 QuestionTwoDemo.java 中添加方法
/** * 查找链表中的倒数第k个节点的方法2 * * @param myLinkedList 需要查找的链表作为参数传递进来 * @param k 代表倒数第k个节点的位置 * @return */ public Node reciprocalFindNode2(MyLinkedList myLinkedList, int k) throws Exception { // 如果头节点为null，说明链表为空 if (myLinkedList.getHeadNode() == null) { throw new Exception("链表为空"); } Node first = myLinkedList.getHeadNode(); Node second = myLinkedList.getHeadNode(); // 让second节点往后挪 k-1 个位置 for (int i = 0; i < k - 1; i++) { second = second.getNext(); } // 让first节点和second节点整体向后移动，直到second节点走到最后一个节点 while (second.getNext() != null) { first = first.getNext(); second = second.getNext(); } // 当second节点走到最后一个节点时，first节点就是我们要找的节点 return first; }
测试的方法和测试结果跟前面的一样，这里不再详细列出。
3、反转一个单向链表
例如链表：
1 -> 2 -> 3 -> 4
反转之后：
4 -> 3 -> 2 -> 1
思路：
从头到尾遍历原链表的节点，每遍历一个节点，将它放在新链表（实际上并没有创建新链表，这里用新链表来描述只是为了更方便的理解）的最前端。 时间复杂度为O(n)
（注意链表为空和只有一个节点的情况）
示意图一：
示意图二：
示意图三：
如此类推。。。
代码如下：
QuestionThreeDemo.java
import org.junit.Test; public class QuestionThreeDemo { /** * 反转一个单向链表的方法 * * @param myLinkedList * @throws Exception */ public void reverseList(MyLinkedList myLinkedList) throws Exception { // 判断链表是否为null if (myLinkedList == null || myLinkedList.getHeadNode() == null || myLinkedList.getHeadNode().getNext() == null) { throw new Exception("链表为空"); } // 判断链表里是否只有一个节点 if (myLinkedList.getHeadNode().getNext().getNext() == null) { // 链表里只有一个节点，不用反转 return; } // tempNode 从头节点后面的第一个节点开始往后移动 Node tempNode = myLinkedList.getHeadNode().getNext(); // 当前节点的下一个节点 Node nextNode = null; // 反转后新链表的头节点 Node newHeadNode = null; // 遍历链表，每遍历到一个节点都把它放到链表的头节点位置 while (tempNode.getNext() != null) { // 把tempNode在旧链表中的下一个节点暂存起来 nextNode = tempNode.getNext(); // 设置tempNode在新链表中作为头节点的next值 tempNode.setNext(newHeadNode); // 更新newHeadNode的值，下一次循环需要用 newHeadNode = tempNode; // 更新头节点 myLinkedList.setHeadNode(newHeadNode); // tempNode往后移动一个位置 tempNode = nextNode; } // 旧链表的最后一个节点的next为null，要把该节点的next设置为新链表的第二个节点 tempNode.setNext(newHeadNode); // 然后把它放到新链表的第一个节点的位置 myLinkedList.setHeadNode(tempNode); // 新建一个新链表的头节点 newHeadNode = new Node(null, tempNode); myLinkedList.setHeadNode(newHeadNode); } /** * 用来测试的方法 */ @Test public void test() throws Exception { MyLinkedList myLinkedList = new MyLinkedList(); Node newNode1 = new Node("欧阳锋", null); Node newNode2 = new Node("黄药师", null); Node newNode3 = new Node("洪七公", null); myLinkedList.insert(newNode1, 1); myLinkedList.insert(newNode2, 2); myLinkedList.insert(newNode3, 3); System.out.println("-----完整的链表start-----"); myLinkedList.showAll(); System.out.println("-----完整的链表end-------"); System.out.println(""); System.out.println("-----反转之后的链表start-----"); reverseList(myLinkedList); myLinkedList.showAll(); System.out.println("-----反转之后的链表end-------"); } }
测试结果：
4、合并两个有序的单向链表，合并之后的链表依然有序
5、找出两个单向链表相交的第一个公共节点
欢迎转载，但请保留文章原始出处
本文地址：
版权声明：本文为nnngu原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。