作者：nnngu
GitHub：https://github.com/nnngu
博客園：http://www.cnblogs.com/nnngu
簡書：http://www.itdecent.cn/users/1df20d76ea5c
知乎：https://www.zhihu.com/people/nnngu/posts

這篇文章包含的鏈表面試題如下：

1、從尾到頭打印單向鏈表

2、查找單向鏈表中的倒數(shù)第k個節(jié)點

3、反轉(zhuǎn)一個單向鏈表【出現(xiàn)頻率較高】

4、合并兩個有序的單向鏈表，合并之后的鏈表依然有序【出現(xiàn)頻率較高】

5、找出兩個單向鏈表相交的第一個公共節(jié)點

前期代碼準(zhǔn)備：

下面這兩個類的詳細解析可以參考我的上一篇文章：數(shù)據(jù)結(jié)構(gòu)3 線性表之鏈表

節(jié)點類：Node.java

/**
 * 節(jié)點類
 */
public class Node {
    Object element; // 數(shù)據(jù)域
    Node next; // 地址域

    // 節(jié)點的構(gòu)造方法
    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 {

    // 頭節(jié)點
    private Node headNode;
    // 用來遍歷鏈表的臨時節(jié)點
    private Node tempNode;

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

    // 鏈表的初始化方法
    public MyLinkedList() {
        // 初始化時，鏈表里面只有1個節(jié)點，所以這個節(jié)點的地址域為null
        Node node = new Node("王重陽", null);
        // 頭節(jié)點不存儲數(shù)據(jù)，它的數(shù)據(jù)域為null，它的地址域存儲了第1個節(jié)點的地址
        headNode = new Node(null, node);
    }

    /**
     * 1、插入節(jié)點：時間復(fù)雜度為O(n)
     * @param newNode 需要插入的新節(jié)點
     * @param position 這個變量的范圍可以從0到鏈表的長度，注意不要越界。
     *                 頭節(jié)點不算進鏈表的長度，
     *                 所以從頭節(jié)點后面的節(jié)點開始算起，position為0
     */
    public void insert(Node newNode, int position) {
        // 通過position變量，讓tempNode節(jié)點從頭節(jié)點開始遍歷，移動到要插入位置的前一個位置
        tempNode = headNode;
        int i = 0;
        while (i < position) {
            tempNode = tempNode.next;
            i++;
        }
        newNode.next = tempNode.next;
        tempNode.next = newNode;
    }

    /**
     * 2、刪除節(jié)點：時間復(fù)雜度為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、查找節(jié)點：時間復(fù)雜度為O(n)
     * @param position
     * @return 返回查找的節(jié)點
     */
    public Node find(int position) {
        // 這里同樣需要用tempNode從頭開始向后查找position
        tempNode = headNode;
        int i = 0;
        while (i < position) {
            tempNode = tempNode.next;
            i++;
        }
        return tempNode.next;
    }

    /**
     * 4、獲取鏈表的長度：時間復(fù)雜度為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記得加上最后一個節(jié)點
        return size;
    }

    // 遍歷鏈表，打印出所有節(jié)點的方法
    public void showAll() {
        tempNode = headNode.next;
        while (tempNode.next != null) {
            System.out.println(tempNode.element);
            tempNode = tempNode.next;
        }
        System.out.println(tempNode.element);
    }
}

1、從尾到頭打印單向鏈表

對于這種顛倒順序打印的問題，我們應(yīng)該就會想到棧，后進先出。因此這一題要么自己新建一個棧，要么使用系統(tǒng)的棧（系統(tǒng)遞歸調(diào)用方法時的棧）。需要把鏈表遍歷完一次，所以它的時間復(fù)雜度為 O(n)

注意：不能先把鏈表反轉(zhuǎn)，再遍歷輸出，因為這樣做會破壞鏈表節(jié)點原來的順序。

方法1：自己新建一個棧

QuestionOneDemo.java

import org.junit.Test;

import java.util.Stack;

public class QuestionOneDemo {

    /**
     * 從尾到頭打印單向鏈表
     * 方法1：自己新建一個棧
     *
     * @param head 參數(shù)為鏈表的頭節(jié)點
     */
    public void reversePrint(Node head) {

        // 判斷鏈表是否為空
        if (head == null) {
            return;
        }

        // 新建一個棧
        Stack<Node> stack = new Stack<Node>();

        // 用來遍歷的臨時節(jié)點，從頭節(jié)點開始
        Node tempNode = head;

        // 從頭節(jié)點開始遍歷鏈表，將除了頭節(jié)點之外的所有節(jié)點壓棧
        while (tempNode.getNext() != null) {
            tempNode = tempNode.getNext();
            stack.push(tempNode);
        }

        // 將棧中的節(jié)點打印輸出即可
        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----");

    }
}

測試結(jié)果：

方法2：使用系統(tǒng)的棧（遞歸）

在 QuestionOneDemo.java 中添加方法2

    /**
     * 從尾到頭打印單向鏈表
     * 方法2：自己新建一個棧
     *
     * @param head 參數(shù)為鏈表的頭節(jié)點
     */
    public void reversePrint2(Node head) {

        // 判斷傳進來的參數(shù)節(jié)點是否為空
        if (head == null) {
            return;
        }

        // 遞歸
        reversePrint2(head.next);
        System.out.println(head.getElement());
    }

測試的方法和測試結(jié)果跟方法1一樣，這里不再詳細列出。

總結(jié)：

方法2是基于遞歸實現(xiàn)的，代碼看起來更簡潔，但有一個問題：當(dāng)鏈表很長的時候，就會導(dǎo)致方法調(diào)用的層級很深，有可能造成棧溢出。而方法1是自己新建一個棧，使用循環(huán)壓棧和循環(huán)出棧，代碼的穩(wěn)健性要更好一些。

2、查找單向鏈表中的倒數(shù)第k個節(jié)點

2-1：普通思路

先將整個鏈表從頭到尾遍歷一次，計算出鏈表的長度size，得到鏈表的長度之后，就好辦了，直接輸出第 size-k 個節(jié)點就可以了（注意鏈表為空，k為0，k大于鏈表中節(jié)點個數(shù)的情況）。因為需要遍歷兩次鏈表，所以時間復(fù)雜度為 T(2n) = O(n)

代碼如下：

QuestionTwoDemo.java

import org.junit.Test;

public class QuestionTwoDemo {

    /**
     * 查找鏈表中的倒數(shù)第k個節(jié)點的方法
     *
     * @param myLinkedList 需要查找的鏈表作為參數(shù)傳遞進來
     * @param k            代表倒數(shù)第k個節(jié)點的位置
     * @return
     */
    public Node reciprocalFindNode(MyLinkedList myLinkedList, int k) throws Exception {
        int size = 0;

        // 如果頭節(jié)點為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不能大于鏈表中節(jié)點的個數(shù)
        if (k > size) {
            throw new Exception("k不能大于鏈表中節(jié)點的個數(shù)");
        }

        // 第二次遍歷，找出倒數(shù)第k個節(jié)點
        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("鏈表的倒數(shù)第1個節(jié)點是：" + node.getElement());

        node = reciprocalFindNode(myLinkedList, 2);
        System.out.println("鏈表的倒數(shù)第2個節(jié)點是：" + node.getElement());

        node = reciprocalFindNode(myLinkedList, 3);
        System.out.println("鏈表的倒數(shù)第3個節(jié)點是：" + node.getElement());

        node = reciprocalFindNode(myLinkedList, 4);
        System.out.println("鏈表的倒數(shù)第4個節(jié)點是：" + node.getElement());
    }
}

測試結(jié)果：

如果面試官不允許你遍歷鏈表的長度，該怎么做？接下來的改進思路就是。

2-2：改進思路

這里需要用到兩個節(jié)點型的變量：即變量 first 和 second，首先讓 first 和 second 都指向第一個節(jié)點，然后讓 second 節(jié)點往后挪 k-1 個位置，此時 first 和 second 就間隔了 k-1 個位置，然后整體向后移動這兩個節(jié)點，直到 second 節(jié)點走到最后一個節(jié)點時，此時 first 節(jié)點所指向的位置就是倒數(shù)第k個節(jié)點的位置。時間復(fù)雜度為O(n)

步驟一：

步驟二：

步驟三：

代碼：

在 QuestionTwoDemo.java 中添加方法

    /**
     * 查找鏈表中的倒數(shù)第k個節(jié)點的方法2
     *
     * @param myLinkedList 需要查找的鏈表作為參數(shù)傳遞進來
     * @param k            代表倒數(shù)第k個節(jié)點的位置
     * @return
     */
    public Node reciprocalFindNode2(MyLinkedList myLinkedList, int k) throws Exception {
        // 如果頭節(jié)點為null，說明鏈表為空
        if (myLinkedList.getHeadNode() == null) {
            throw new Exception("鏈表為空");
        }

        Node first = myLinkedList.getHeadNode();
        Node second = myLinkedList.getHeadNode();

        // 讓second節(jié)點往后挪 k-1 個位置
        for (int i = 0; i < k - 1; i++) {
            second = second.getNext();
        }

        // 讓first節(jié)點和second節(jié)點整體向后移動，直到second節(jié)點走到最后一個節(jié)點
        while (second.getNext() != null) {
            first = first.getNext();
            second = second.getNext();
        }
        // 當(dāng)second節(jié)點走到最后一個節(jié)點時，first節(jié)點就是我們要找的節(jié)點
        return first;
    }

測試的方法和測試結(jié)果跟前面的一樣，這里不再詳細列出。

3、反轉(zhuǎn)一個單向鏈表

例如鏈表：

1 -> 2 -> 3 -> 4

反轉(zhuǎn)之后：

4 -> 3 -> 2 -> 1

思路：

從頭到尾遍歷原鏈表的節(jié)點，每遍歷一個節(jié)點，將它放在新鏈表（實際上并沒有創(chuàng)建新鏈表，這里用新鏈表來描述只是為了更方便的理解）的最前端。 時間復(fù)雜度為O(n)

（注意鏈表為空和只有一個節(jié)點的情況）

示意圖一：

示意圖二：

示意圖三：

如此類推。。。

代碼如下：

QuestionThreeDemo.java

import org.junit.Test;

public class QuestionThreeDemo {

    /**
     * 反轉(zhuǎn)一個單向鏈表的方法
     *
     * @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("鏈表為空");
        }

        // 判斷鏈表里是否只有一個節(jié)點
        if (myLinkedList.getHeadNode().getNext().getNext() == null) {
            // 鏈表里只有一個節(jié)點，不用反轉(zhuǎn)
            return;
        }

        // tempNode 從頭節(jié)點后面的第一個節(jié)點開始往后移動
        Node tempNode = myLinkedList.getHeadNode().getNext();
        // 當(dāng)前節(jié)點的下一個節(jié)點
        Node nextNode = null;
        // 反轉(zhuǎn)后新鏈表的頭節(jié)點
        Node newHeadNode = null;

        // 遍歷鏈表，每遍歷到一個節(jié)點都把它放到鏈表的頭節(jié)點位置
        while (tempNode.getNext() != null) {
            // 把tempNode在舊鏈表中的下一個節(jié)點暫存起來
            nextNode = tempNode.getNext();
            // 設(shè)置tempNode在新鏈表中作為頭節(jié)點的next值
            tempNode.setNext(newHeadNode);
            // 更新newHeadNode的值，下一次循環(huán)需要用
            newHeadNode = tempNode;
            // 更新頭節(jié)點
            myLinkedList.setHeadNode(newHeadNode);
            // tempNode往后移動一個位置
            tempNode = nextNode;
        }
        // 舊鏈表的最后一個節(jié)點的next為null，要把該節(jié)點的next設(shè)置為新鏈表的第二個節(jié)點
        tempNode.setNext(newHeadNode);
        // 然后把它放到新鏈表的第一個節(jié)點的位置
        myLinkedList.setHeadNode(tempNode);
        // 新建一個新鏈表的頭節(jié)點
        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("-----反轉(zhuǎn)之后的鏈表start-----");
        reverseList(myLinkedList);
        myLinkedList.showAll();
        System.out.println("-----反轉(zhuǎn)之后的鏈表end-------");
    }
}

測試結(jié)果：

4、合并兩個有序的單向鏈表，合并之后的鏈表依然有序

例如有：

鏈表1：

1 -> 2 -> 3 -> 4

鏈表2：

2 -> 3 -> 4 -> 5

合并后：

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

思路：

挨著比較鏈表1和鏈表2。

要注意兩個鏈表都為空、或其中一個鏈表為空的情況。時間復(fù)雜度為 O(max(len1, len2))

4-1：示意圖

步驟一：head1和head2對比，選出一個較小的，放入新鏈表

步驟二：head1和head2對比，選出一個較小的，放入新鏈表

步驟三：head1和head2對比，選出一個較小的，放入新鏈表

步驟四：head1和head2對比，選出一個較小的，放入新鏈表

步驟五：head1和head2對比，選出一個較小的，放入新鏈表

如此類推，temp在鏈表1和鏈表2之間移動，選出較小的節(jié)點，放到新鏈表的后面。

4-2：代碼實現(xiàn)

節(jié)點類：NumberNode.java

public class NumberNode {
    Integer element; // 數(shù)據(jù)域
    NumberNode next; // 地址域

    // 節(jié)點的構(gòu)造方法
    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 {
    // 頭節(jié)點
    private NumberNode headNode;
    // 用來遍歷鏈表的臨時節(jié)點
    private NumberNode tempNode;

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

    // 鏈表的初始化方法
    public MyNumberLinkedList() {
        // 初始化時，鏈表里面只有1個節(jié)點，所以這個節(jié)點的地址域為null
        NumberNode node = new NumberNode(0, null);
        // 頭節(jié)點不存儲數(shù)據(jù)，它的數(shù)據(jù)域為null，它的地址域存儲了第1個節(jié)點的地址
        headNode = new NumberNode(null, node);
    }

    /**
     * 1、插入節(jié)點：時間復(fù)雜度為O(n)
     * @param newNode 需要插入的新節(jié)點
     * @param position 這個變量的范圍可以從0到鏈表的長度，注意不要越界。
     *                 頭節(jié)點不算進鏈表的長度，
     *                 所以從頭節(jié)點后面的節(jié)點開始算起，position為0
     */
    public void insert(NumberNode newNode, int position) {
        // 通過position變量，讓tempNode節(jié)點從頭節(jié)點開始遍歷，移動到要插入位置的前一個位置
        tempNode = headNode;
        int i = 0;
        while (i < position) {
            tempNode = tempNode.next;
            i++;
        }
        newNode.next = tempNode.next;
        tempNode.next = newNode;
    }

    /**
     * 2、刪除節(jié)點：時間復(fù)雜度為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、查找節(jié)點：時間復(fù)雜度為O(n)
     * @param position
     * @return 返回查找的節(jié)點
     */
    public NumberNode find(int position) {
        // 這里同樣需要用tempNode從頭開始向后查找position
        tempNode = headNode;
        int i = 0;
        while (i < position) {
            tempNode = tempNode.next;
            i++;
        }
        return tempNode.next;
    }

    /**
     * 4、獲取鏈表的長度：時間復(fù)雜度為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記得加上最后一個節(jié)點
        return size;
    }

    // 遍歷鏈表，打印出所有節(jié)點的方法
    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的第一個有效節(jié)點(注意與頭節(jié)點的區(qū)分！)
     * @param head2 有序鏈表2的第一個有效節(jié)點(注意與頭節(jié)點的區(qū)分！)
     * @return 返回合并好的有序鏈表的第一個有效節(jié)點(注意與頭節(jié)點的區(qū)分！)
     * @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;
        }

        // 新鏈表的第一個有效節(jié)點(注意與頭節(jié)點的區(qū)分！)
        NumberNode newHead;
        // temp指針會在兩個鏈表中來回選出較小的節(jié)點
        NumberNode temp;

        // 一開始，讓temp指針指向head1和head2中較小的數(shù)據(jù)，得到head節(jié)點
        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指針的下一個節(jié)點對應(yīng)較小的那個數(shù)據(jù)
                temp.setNext(head1);
                // temp指針往后移
                temp = temp.getNext();
                // head1也要往后移
                head1 = head1.getNext();
            } else {
                temp.setNext(head2);
                temp = temp.getNext();
                head2 = head2.getNext();
            }
        }

        // 合并剩下的節(jié)點，剩下的節(jié)點一定是都在同一個鏈表中
        // 如果head1不為空，說明鏈表1里面還有節(jié)點，鏈表2已經(jīng)被遍歷完了
        if (head1 != null) {
            temp.setNext(head1);
        }
        if (head2 != null) {
            temp.setNext(head2);
        }
        // 返回新鏈表的第一個有效節(jié)點(注意與頭節(jié)點的區(qū)分！)
        return newHead;
    }

    /**
     * 用來測試的方法
     */
    @Test
    public void test() throws Exception {
        MyNumberLinkedList list1 = new MyNumberLinkedList();
        MyNumberLinkedList list2 = new MyNumberLinkedList();

        // 向鏈表1中添加數(shù)據(jù)
        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中添加數(shù)據(jù)
        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();
    }
}

測試結(jié)果：

5、找出兩個單向鏈表相交的第一個公共節(jié)點

5-1：示意圖

兩個節(jié)點相交的第一個公共節(jié)點如下圖：

5-2：思路

方法一：

面試時，很多人碰到這道題的第一反應(yīng)是：在第一個鏈表上順序遍歷每個節(jié)點，每遍歷到一個節(jié)點的時候，在第二個鏈表上順序遍歷每個節(jié)點。如果在第二個鏈表上有一個節(jié)點和第一個鏈表上的節(jié)點一樣，說明兩個鏈表在這個節(jié)點上重合。所以這種方法的時間復(fù)雜度為 O(len1 * len2)

方法二：（用棧）

參考上面的示意圖，如果兩個鏈表有公共節(jié)點，那么最后一個節(jié)點（節(jié)點7）一定是一樣的，而且是從中間的某一個節(jié)點（節(jié)點6）開始，后面的節(jié)點都是一樣的。

現(xiàn)在的問題是，在單鏈表中，我們只能從頭節(jié)點開始順序遍歷，最后才能到達尾節(jié)點。最后到達的尾節(jié)點卻要先被比較，這聽起來是不是像“先進后出”？于是我們就能想到利用棧來解決這個問題：分別把兩個鏈表的節(jié)點放入兩個棧中，這樣兩個鏈表的尾節(jié)點就位于兩個棧的棧頂，接下來從兩個棧的棧頂開始比較，直到找到最后一個相同的節(jié)點，就是他們的公共點。

這種方法中，我們需要利用兩個輔助棧，空間復(fù)雜度是 O(len1+len2)，時間復(fù)雜度是 O(len1+len2)。跟方法一相比，時間效率得到了提高，相當(dāng)于利用空間來換取時間。

那么，有沒有更好的方法呢？接下來要講。

方法三：（快慢指針）****

其實我們還有一個更簡單的方法：首先遍歷兩個鏈表得到它們的長度。在第二次遍歷的時候，在較長的鏈表上走 |len1-len2| 步，然后再同時遍歷這兩個鏈表，找到的第一個相同的節(jié)點就是它們的第一個公共點。

這種方法的時間復(fù)雜度也是 O(len1+len2)，但是我們不再需要用兩個棧，因此提高了空間效率。當(dāng)面試官肯定了我們的最后一種思路的時候，就可以動手寫代碼了。

5-3：代碼

這里我只寫方法三的實現(xiàn)代碼：

QuestionFiveDemo.java

import org.junit.Test;

public class QuestionFiveDemo {

    /**
     * 方法：求兩個鏈表相交的第一個公共節(jié)點
     *
     * @param head1 鏈表1頭節(jié)點后面的第一個節(jié)點
     * @param head2 鏈表2頭節(jié)點后面的第一個節(jié)點
     * @return 返回兩個鏈表的第一個公共節(jié)點
     */
    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) {
            // 第一個相同的節(jié)點就是它們的公共節(jié)點
            if (longHead.getElement() == shortHead.getElement()) {
                return longHead;
            }
            longHead = longHead.getNext();
            shortHead = shortHead.getNext();
        }
        return null;
    }

    /**
     * 方法：獲取鏈表的長度
     *
     * @param head 指頭節(jié)點后面的第一個節(jié)點
     * @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中添加數(shù)據(jù)
        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中添加數(shù)據(jù)
        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("");

        // 輸出第一個公共節(jié)點
        NumberNode commonNode = getFirstCommonNode(node1_1, node2_4);
        System.out.println("第一個公共節(jié)點是：" + commonNode.getElement());
    }
}

測試結(jié)果：