数据结构04 链表的面试题

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

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、合并两个有序的单向链表，合并之后的链表依然有序

例如有：

链表1：

　　1 -> 2 -> 3 -> 4

链表2：

　　2 -> 3 -> 4 -> 5

合并后：

　　1 -> 2 -> 2 -> 3 -> 3 -> 4 -> 4 -> 5

思路：

　　挨着比较链表1和链表2。

　　要注意两个链表都为空、或其中一个链表为空的情况。时间复杂度为 O(max(len1, len2)) 

4-1：示意图

步骤一：head1和head2对比，选出一个较小的，放入新链表

步骤二：head1和head2对比，选出一个较小的，放入新链表

步骤三：head1和head2对比，选出一个较小的，放入新链表

步骤四：head1和head2对比，选出一个较小的，放入新链表

步骤五：head1和head2对比，选出一个较小的，放入新链表

如此类推，temp在链表1和链表2之间移动，选出较小的节点，放到新链表的后面。

4-2：代码实现

 节点类：NumberNode.java

public class NumberNode {
    Integer element; // 数据域
    NumberNode next; // 地址域

    // 节点的构造方法
    public NumberNode(Integer element, NumberNode next) {
        this.element = element;
        this.next = next;
    }

    // Gettet and Setter
    public Integer getElement() {
        return element;
    }

    public void setElement(Integer element) {
        this.element = element;
    }

    public NumberNode getNext() {
        return next;
    }

    public void setNext(NumberNode next) {
        this.next = next;
    }
}

链表类：MyNumberLinkedList.java

public class MyNumberLinkedList {
    // 头节点
    private NumberNode headNode;
    // 用来遍历链表的临时节点
    private NumberNode tempNode;

    // Getter
    public NumberNode getHeadNode() {
        return headNode;
    }
    // Setter
    public void setHeadNode(NumberNode headNode) {
        this.headNode = headNode;
    }

    // 链表的初始化方法
    public MyNumberLinkedList() {
        // 初始化时，链表里面只有1个节点，所以这个节点的地址域为null
        NumberNode node = new NumberNode(0, null);
        // 头节点不存储数据，它的数据域为null，它的地址域存储了第1个节点的地址
        headNode = new NumberNode(null, node);
    }

    /**
     * 1、插入节点：时间复杂度为O(n)
     * @param newNode 需要插入的新节点
     * @param position 这个变量的范围可以从0到链表的长度，注意不要越界。
     *                 头节点不算进链表的长度，
     *                 所以从头节点后面的节点开始算起，position为0
     */
    public void insert(NumberNode 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 NumberNode 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);
    }
}

解答方法：QuestionFourDemo.java

import org.junit.Test;

public class QuestionFourDemo {

    /**
     * 合并两个有序链表，使合并之后的链表依然有序
     *
     * @param head1 有序链表1的第一个有效节点(注意与头节点的区分！)
     * @param head2 有序链表2的第一个有效节点(注意与头节点的区分！)
     * @return 返回合并好的有序链表的第一个有效节点(注意与头节点的区分！)
     * @throws Exception
     */
    public NumberNode mergeLinkedList(NumberNode head1, NumberNode head2) throws Exception {
        // 如果两个链表都为空
        if (head1 == null && head2 == null) {
            throw new Exception("两个链表都为空");
        }
        if (head1 == null) {
            return head2;
        }
        if (head2 == null) {
            return head1;
        }

        // 新链表的第一个有效节点(注意与头节点的区分！)
        NumberNode newHead;
        // temp指针会在两个链表中来回选出较小的节点
        NumberNode temp;

        // 一开始，让temp指针指向head1和head2中较小的数据，得到head节点
        if (head1.getElement() < head2.getElement()) {
            newHead = head1;
            temp = head1;
            head1 = head1.getNext();
        } else {
            newHead = head2;
            temp = head2;
            head2 = head2.getNext();
        }

        while (head1 != null && head2 != null) {
            if (head1.getElement() < head2.getElement()) {
                // temp指针的下一个节点对应较小的那个数据
                temp.setNext(head1);
                // temp指针往后移
                temp = temp.getNext();
                // head1也要往后移
                head1 = head1.getNext();
            } else {
                temp.setNext(head2);
                temp = temp.getNext();
                head2 = head2.getNext();
            }
        }

        // 合并剩下的节点，剩下的节点一定是都在同一个链表中
        // 如果head1不为空，说明链表1里面还有节点，链表2已经被遍历完了
        if (head1 != null) {
            temp.setNext(head1);
        }
        if (head2 != null) {
            temp.setNext(head2);
        }
        // 返回新链表的第一个有效节点(注意与头节点的区分！)
        return newHead;
    }

    /**
     * 用来测试的方法
     */
    @Test
    public void test() throws Exception {
        MyNumberLinkedList list1 = new MyNumberLinkedList();
        MyNumberLinkedList list2 = new MyNumberLinkedList();

        // 向链表1中添加数据
        NumberNode node1_1 = new NumberNode(1, null);
        NumberNode node1_2 = new NumberNode(2, null);
        NumberNode node1_3 = new NumberNode(3, null);
        NumberNode node1_4 = new NumberNode(4, null);
        list1.insert(node1_1, 1);
        list1.insert(node1_2, 2);
        list1.insert(node1_3, 3);
        list1.insert(node1_4, 4);

        // 向链表2中添加数据
        NumberNode node2_2 = new NumberNode(2, null);
        NumberNode node2_3 = new NumberNode(3, null);
        NumberNode node2_4 = new NumberNode(4, null);
        NumberNode node2_5 = new NumberNode(5, null);
        list2.insert(node2_2, 1);
        list2.insert(node2_3, 2);
        list2.insert(node2_4, 3);
        list2.insert(node2_5, 4);

        // 分别输出链表1和链表2
        System.out.println("链表1：");
        list1.showAll();
        System.out.println("");
        System.out.println("链表2：");
        list2.showAll();
        System.out.println("");

        // 合并之后输出
        System.out.println("合并之后的链表：");
        NumberNode newNode = mergeLinkedList(list1.getHeadNode().getNext(), list2.getHeadNode().getNext());
        NumberNode newHeadNode = new NumberNode(null, newNode);
        MyNumberLinkedList newList = new MyNumberLinkedList();
        newList.setHeadNode(newHeadNode);
        newList.showAll();
    }
}

测试结果：

  

5、找出两个单向链表相交的第一个公共节点

5-1：示意图

两个节点相交的第一个公共节点如下图：

5-2：思路

方法一：

面试时，很多人碰到这道题的第一反应是：在第一个链表上顺序遍历每个节点，每遍历到一个节点的时候，在第二个链表上顺序遍历每个节点。如果在第二个链表上有一个节点和第一个链表上的节点一样，说明两个链表在这个节点上重合。所以这种方法的时间复杂度为 O(len1 * len2)  

方法二：（用栈）

参考上面的示意图，如果两个链表有公共节点，那么最后一个节点（节点7）一定是一样的，而且是从中间的某一个节点（节点6）开始，后面的节点都是一样的。

现在的问题是，在单链表中，我们只能从头节点开始顺序遍历，最后才能到达尾节点。最后到达的尾节点却要先被比较，这听起来是不是像“先进后出”？于是我们就能想到利用栈来解决这个问题：分别把两个链表的节点放入两个栈中，这样两个链表的尾节点就位于两个栈的栈顶，接下来从两个栈的栈顶开始比较，直到找到最后一个相同的节点，就是他们的公共点。

这种方法中，我们需要利用两个辅助栈，空间复杂度是 O(len1+len2)，时间复杂度是 O(len1+len2)。跟方法一相比，时间效率得到了提高，相当于利用空间来换取时间。

那么，有没有更好的方法呢？接下来要讲。

方法三：（快慢指针）

其实我们还有一个更简单的方法：首先遍历两个链表得到它们的长度。在第二次遍历的时候，在较长的链表上走 |len1-len2| 步，然后再同时遍历这两个链表，找到的第一个相同的节点就是它们的第一个公共点。 

这种方法的时间复杂度也是 O(len1+len2)，但是我们不再需要用两个栈，因此提高了空间效率。当面试官肯定了我们的最后一种思路的时候，就可以动手写代码了。 

5-3：代码

这里我只写方法三的实现代码：

QuestionFiveDemo.java

import org.junit.Test;

public class QuestionFiveDemo {

    /**
     * 方法：求两个链表相交的第一个公共节点
     *
     * @param head1 链表1头节点后面的第一个节点
     * @param head2 链表2头节点后面的第一个节点
     * @return 返回两个链表的第一个公共节点
     */
    public NumberNode getFirstCommonNode(NumberNode head1, NumberNode head2) {
        if (head1 == null || head2 == null) {
            return null;
        }

        int size1 = getSize(head1);
        int size2 = getSize(head2);
        // 两个链表长度的差值
        int diffSize = 0;

        NumberNode longHead;
        NumberNode shortHead;

        // 找出较长的那个链表
        if (size1 > size2) {
            longHead = head1;
            shortHead = head2;
            diffSize = size1 - size2;
        } else {
            longHead = head2;
            shortHead = head1;
            diffSize = size2 - size1;
        }

        // 把较长的那个链表的指针向后移动diffSize个位置
        for (int i = 0; i < diffSize; i++) {
            longHead = longHead.getNext();
        }

        // 两个链表的指针同时向后移动
        while (longHead != null && shortHead != null) {
            // 第一个相同的节点就是它们的公共节点
            if (longHead.getElement() == shortHead.getElement()) {
                return longHead;
            }
            longHead = longHead.getNext();
            shortHead = shortHead.getNext();
        }
        return null;
    }

    /**
     * 方法：获取链表的长度
     *
     * @param head 指头节点后面的第一个节点
     * @return 返回链表的长度
     */
    public int getSize(NumberNode head) {
        if (head == null) {
            return 0;
        }

        int size = 0;
        NumberNode temp = head;
        while (temp != null) {
            size++;
            temp = temp.getNext();
        }
        return size;
    }

    /**
     * 用来测试的方法
     */
    @Test
    public void test() throws Exception {
        MyNumberLinkedList list1 = new MyNumberLinkedList();
        MyNumberLinkedList list2 = new MyNumberLinkedList();

        // 向链表1中添加数据
        NumberNode node1_1 = new NumberNode(1, null);
        NumberNode node1_2 = new NumberNode(2, null);
        NumberNode node1_3 = new NumberNode(3, null);
        NumberNode node1_4 = new NumberNode(6, null);
        NumberNode node1_5 = new NumberNode(7, null);
        list1.insert(node1_1, 1);
        list1.insert(node1_2, 2);
        list1.insert(node1_3, 3);
        list1.insert(node1_4, 4);
        list1.insert(node1_5, 5);

        // 向链表2中添加数据
        NumberNode node2_4 = new NumberNode(4, null);
        NumberNode node2_5 = new NumberNode(5, null);
        NumberNode node2_6 = new NumberNode(6, null);
        NumberNode node2_7 = new NumberNode(7, null);
        list2.insert(node2_4, 1);
        list2.insert(node2_5, 2);
        list2.insert(node2_6, 3);
        list2.insert(node2_7, 4);

        // 分别输出链表1和链表2
        System.out.println("链表1：");
        list1.showAll();
        System.out.println("");
        System.out.println("链表2：");
        list2.showAll();
        System.out.println("");

        // 输出第一个公共节点
        NumberNode commonNode = getFirstCommonNode(node1_1, node2_4);
        System.out.println("第一个公共节点是：" + commonNode.getElement());
    }
}

测试结果：

欢迎转载，但请保留文章原始出处

本文地址：http://www.cnblogs.com/nnngu/p/8264766.html