这篇文章包含的链表面试题如下：

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、找出两个单向链表相交的个公共节