作者：nnngu
GitHub：https://github.com/nnngu
博客園：http://www.cnblogs.com/nnngu
簡書：http://www.reibang.com/users/1df20d76ea5c
知乎：https://www.zhihu.com/people/nnngu/posts
這篇文章包含的鏈表面試題如下：
1岛马、從尾到頭打印單向鏈表
2、查找單向鏈表中的倒數(shù)第k個(gè)節(jié)點(diǎn)
3瓣赂、反轉(zhuǎn)一個(gè)單向鏈表【出現(xiàn)頻率較高】
4、合并兩個(gè)有序的單向鏈表，合并之后的鏈表依然有序【出現(xiàn)頻率較高】
5、找出兩個(gè)單向鏈表相交的第一個(gè)公共節(jié)點(diǎn)
前期代碼準(zhǔn)備：
下面這兩個(gè)類的詳細(xì)解析可以參考我的上一篇文章：數(shù)據(jù)結(jié)構(gòu)3 線性表之鏈表
節(jié)點(diǎn)類：Node.java
/**
* 節(jié)點(diǎn)類
*/
public class Node {
Object element; // 數(shù)據(jù)域
Node next; // 地址域
// 節(jié)點(diǎn)的構(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
/**
* 自己定義的一個(gè)鏈表類
*/
public class MyLinkedList {
// 頭節(jié)點(diǎn)
private Node headNode;
// 用來遍歷鏈表的臨時(shí)節(jié)點(diǎn)
private Node tempNode;
// Getter
public Node getHeadNode() {
return headNode;
}
// Setter
public void setHeadNode(Node headNode) {
this.headNode = headNode;
}
// 鏈表的初始化方法
public MyLinkedList() {
// 初始化時(shí)疯汁，鏈表里面只有1個(gè)節(jié)點(diǎn)，所以這個(gè)節(jié)點(diǎn)的地址域?yàn)閚ull
Node node = new Node("王重陽", null);
// 頭節(jié)點(diǎn)不存儲數(shù)據(jù)卵酪，它的數(shù)據(jù)域?yàn)閚ull幌蚊，它的地址域存儲了第1個(gè)節(jié)點(diǎn)的地址
headNode = new Node(null, node);
}
/**
* 1、插入節(jié)點(diǎn)：時(shí)間復(fù)雜度為O(n)
* @param newNode 需要插入的新節(jié)點(diǎn)
* @param position 這個(gè)變量的范圍可以從0到鏈表的長度溃卡，注意不要越界溢豆。
* 頭節(jié)點(diǎn)不算進(jìn)鏈表的長度，
* 所以從頭節(jié)點(diǎn)后面的節(jié)點(diǎn)開始算起瘸羡，position為0
*/
public void insert(Node newNode, int position) {
// 通過position變量漩仙，讓tempNode節(jié)點(diǎn)從頭節(jié)點(diǎn)開始遍歷，移動到要插入位置的前一個(gè)位置
tempNode = headNode;
int i = 0;
while (i < position) {
tempNode = tempNode.next;
i++;
}
newNode.next = tempNode.next;
tempNode.next = newNode;
}
/**
* 2、刪除節(jié)點(diǎn)：時(shí)間復(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é)點(diǎn)：時(shí)間復(fù)雜度為O(n)
* @param position
* @return 返回查找的節(jié)點(diǎn)
*/
public Node find(int position) {
// 這里同樣需要用tempNode從頭開始向后查找position
tempNode = headNode;
int i = 0;
while (i < position) {
tempNode = tempNode.next;
i++;
}
return tempNode.next;
}
/**
* 4卷仑、獲取鏈表的長度：時(shí)間復(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的地址域?yàn)閚ull時(shí)，size記得加上最后一個(gè)節(jié)點(diǎn)
return size;
}
// 遍歷鏈表麸折，打印出所有節(jié)點(diǎn)的方法
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)該就會想到棧垢啼，后進(jìn)先出窜锯。因此這一題要么自己新建一個(gè)棧，要么使用系統(tǒng)的棧（系統(tǒng)遞歸調(diào)用方法時(shí)的棧）芭析。需要把鏈表遍歷完一次锚扎，所以它的時(shí)間復(fù)雜度為 O(n)
注意：不能先把鏈表反轉(zhuǎn)，再遍歷輸出馁启，因?yàn)檫@樣做會破壞鏈表節(jié)點(diǎn)原來的順序驾孔。
方法1：自己新建一個(gè)棧
QuestionOneDemo.java
import org.junit.Test;
import java.util.Stack;
public class QuestionOneDemo {
/**
* 從尾到頭打印單向鏈表
* 方法1：自己新建一個(gè)棧
*
* @param head 參數(shù)為鏈表的頭節(jié)點(diǎn)
*/
public void reversePrint(Node head) {
// 判斷鏈表是否為空
if (head == null) {
return;
}
// 新建一個(gè)棧
Stack<Node> stack = new Stack<Node>();
// 用來遍歷的臨時(shí)節(jié)點(diǎn)，從頭節(jié)點(diǎn)開始
Node tempNode = head;
// 從頭節(jié)點(diǎn)開始遍歷鏈表进统，將除了頭節(jié)點(diǎn)之外的所有節(jié)點(diǎn)壓棧
while (tempNode.getNext() != null) {
tempNode = tempNode.getNext();
stack.push(tempNode);
}
// 將棧中的節(jié)點(diǎn)打印輸出即可
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：自己新建一個(gè)棧
*
* @param head 參數(shù)為鏈表的頭節(jié)點(diǎn)
*/
public void reversePrint2(Node head) {
// 判斷傳進(jìn)來的參數(shù)節(jié)點(diǎn)是否為空
if (head == null) {
return;
}
// 遞歸
reversePrint2(head.next);
System.out.println(head.getElement());
}
測試的方法和測試結(jié)果跟方法1一樣助币，這里不再詳細(xì)列出。
總結(jié)：
方法2是基于遞歸實(shí)現(xiàn)的螟碎，代碼看起來更簡潔眉菱，但有一個(gè)問題：當(dāng)鏈表很長的時(shí)候，就會導(dǎo)致方法調(diào)用的層級很深掉分，有可能造成棧溢出俭缓。而方法1是自己新建一個(gè)棧，使用循環(huán)壓棧和循環(huán)出棧酥郭，代碼的穩(wěn)健性要更好一些华坦。
2、查找單向鏈表中的倒數(shù)第k個(gè)節(jié)點(diǎn)
2-1：普通思路
先將整個(gè)鏈表從頭到尾遍歷一次不从，計(jì)算出鏈表的長度size惜姐，得到鏈表的長度之后，就好辦了椿息，直接輸出第 size-k 個(gè)節(jié)點(diǎn)就可以了（注意鏈表為空歹袁，k為0，k大于鏈表中節(jié)點(diǎn)個(gè)數(shù)的情況）寝优。因?yàn)樾枰闅v兩次鏈表条舔，所以時(shí)間復(fù)雜度為 T(2n) = O(n)
代碼如下：
QuestionTwoDemo.java
import org.junit.Test;
public class QuestionTwoDemo {
/**
* 查找鏈表中的倒數(shù)第k個(gè)節(jié)點(diǎn)的方法
*
* @param myLinkedList 需要查找的鏈表作為參數(shù)傳遞進(jìn)來
* @param k 代表倒數(shù)第k個(gè)節(jié)點(diǎn)的位置
* @return
*/
public Node reciprocalFindNode(MyLinkedList myLinkedList, int k) throws Exception {
int size = 0;
// 如果頭節(jié)點(diǎn)為null，說明鏈表為空
if (myLinkedList.getHeadNode() == null) {
throw new Exception("鏈表為空");
}
// 判斷k乏矾，k不能為0
if (k == 0) {
throw new Exception("k不能為0");
}
// 第一次遍歷孟抗，計(jì)算出鏈表的長度size
Node tempNode = myLinkedList.getHeadNode();
while (tempNode != null) {
size++;
tempNode = tempNode.getNext();
}
// 判斷k迁杨，k不能大于鏈表中節(jié)點(diǎn)的個(gè)數(shù)
if (k > size) {
throw new Exception("k不能大于鏈表中節(jié)點(diǎn)的個(gè)數(shù)");
}
// 第二次遍歷，找出倒數(shù)第k個(gè)節(jié)點(diǎn)
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個(gè)節(jié)點(diǎn)是：" + node.getElement());
node = reciprocalFindNode(myLinkedList, 2);
System.out.println("鏈表的倒數(shù)第2個(gè)節(jié)點(diǎn)是：" + node.getElement());
node = reciprocalFindNode(myLinkedList, 3);
System.out.println("鏈表的倒數(shù)第3個(gè)節(jié)點(diǎn)是：" + node.getElement());
node = reciprocalFindNode(myLinkedList, 4);
System.out.println("鏈表的倒數(shù)第4個(gè)節(jié)點(diǎn)是：" + node.getElement());
}
}
測試結(jié)果：
如果面試官不允許你遍歷鏈表的長度凄硼，該怎么做铅协？接下來的改進(jìn)思路就是。
2-2：改進(jìn)思路
這里需要用到兩個(gè)節(jié)點(diǎn)型的變量：即變量 first 和 second摊沉，首先讓 first 和 second 都指向第一個(gè)節(jié)點(diǎn)警医，然后讓 second 節(jié)點(diǎn)往后挪 k-1 個(gè)位置，此時(shí) first 和 second 就間隔了 k-1 個(gè)位置坯钦，然后整體向后移動這兩個(gè)節(jié)點(diǎn)，直到 second 節(jié)點(diǎn)走到最后一個(gè)節(jié)點(diǎn)時(shí)侈玄，此時(shí) first 節(jié)點(diǎn)所指向的位置就是倒數(shù)第k個(gè)節(jié)點(diǎn)的位置婉刀。時(shí)間復(fù)雜度為O(n)
步驟一：
步驟二：
步驟三：
代碼：
在 QuestionTwoDemo.java 中添加方法
/**
* 查找鏈表中的倒數(shù)第k個(gè)節(jié)點(diǎn)的方法2
*
* @param myLinkedList 需要查找的鏈表作為參數(shù)傳遞進(jìn)來
* @param k 代表倒數(shù)第k個(gè)節(jié)點(diǎn)的位置
* @return
*/
public Node reciprocalFindNode2(MyLinkedList myLinkedList, int k) throws Exception {
// 如果頭節(jié)點(diǎn)為null，說明鏈表為空
if (myLinkedList.getHeadNode() == null) {
throw new Exception("鏈表為空");
}
Node first = myLinkedList.getHeadNode();
Node second = myLinkedList.getHeadNode();
// 讓second節(jié)點(diǎn)往后挪 k-1 個(gè)位置
for (int i = 0; i < k - 1; i++) {
second = second.getNext();
}
// 讓first節(jié)點(diǎn)和second節(jié)點(diǎn)整體向后移動序仙，直到second節(jié)點(diǎn)走到最后一個(gè)節(jié)點(diǎn)
while (second.getNext() != null) {
first = first.getNext();
second = second.getNext();
}
// 當(dāng)second節(jié)點(diǎn)走到最后一個(gè)節(jié)點(diǎn)時(shí)突颊，first節(jié)點(diǎn)就是我們要找的節(jié)點(diǎn)
return first;
}
測試的方法和測試結(jié)果跟前面的一樣，這里不再詳細(xì)列出潘悼。
3律秃、反轉(zhuǎn)一個(gè)單向鏈表
例如鏈表：
1 -> 2 -> 3 -> 4
反轉(zhuǎn)之后：
4 -> 3 -> 2 -> 1
思路：
從頭到尾遍歷原鏈表的節(jié)點(diǎn)，每遍歷一個(gè)節(jié)點(diǎn)治唤，將它放在新鏈表（實(shí)際上并沒有創(chuàng)建新鏈表棒动，這里用新鏈表來描述只是為了更方便的理解）的最前端。 時(shí)間復(fù)雜度為O(n)
（注意鏈表為空和只有一個(gè)節(jié)點(diǎn)的情況）
示意圖一：
示意圖二：
示意圖三：
如此類推宾添。船惨。。
代碼如下：
QuestionThreeDemo.java
import org.junit.Test;
public class QuestionThreeDemo {
/**
* 反轉(zhuǎn)一個(gè)單向鏈表的方法
*
* @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("鏈表為空");
}
// 判斷鏈表里是否只有一個(gè)節(jié)點(diǎn)
if (myLinkedList.getHeadNode().getNext().getNext() == null) {
// 鏈表里只有一個(gè)節(jié)點(diǎn)缕陕，不用反轉(zhuǎn)
return;
}
// tempNode 從頭節(jié)點(diǎn)后面的第一個(gè)節(jié)點(diǎn)開始往后移動
Node tempNode = myLinkedList.getHeadNode().getNext();
// 當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
Node nextNode = null;
// 反轉(zhuǎn)后新鏈表的頭節(jié)點(diǎn)
Node newHeadNode = null;
// 遍歷鏈表粱锐，每遍歷到一個(gè)節(jié)點(diǎn)都把它放到鏈表的頭節(jié)點(diǎn)位置
while (tempNode.getNext() != null) {
// 把tempNode在舊鏈表中的下一個(gè)節(jié)點(diǎn)暫存起來
nextNode = tempNode.getNext();
// 設(shè)置tempNode在新鏈表中作為頭節(jié)點(diǎn)的next值
tempNode.setNext(newHeadNode);
// 更新newHeadNode的值，下一次循環(huán)需要用
newHeadNode = tempNode;
// 更新頭節(jié)點(diǎn)
myLinkedList.setHeadNode(newHeadNode);
// tempNode往后移動一個(gè)位置
tempNode = nextNode;
}
// 舊鏈表的最后一個(gè)節(jié)點(diǎn)的next為null扛邑，要把該節(jié)點(diǎn)的next設(shè)置為新鏈表的第二個(gè)節(jié)點(diǎn)
tempNode.setNext(newHeadNode);
// 然后把它放到新鏈表的第一個(gè)節(jié)點(diǎn)的位置
myLinkedList.setHeadNode(tempNode);
// 新建一個(gè)新鏈表的頭節(jié)點(diǎn)
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怜浅、合并兩個(gè)有序的單向鏈表，合并之后的鏈表依然有序
例如有：
鏈表1：
1 -> 2 -> 3 -> 4
鏈表2：
2 -> 3 -> 4 -> 5
合并后：
1 -> 2 -> 2 -> 3 -> 3 -> 4 -> 4 -> 5
思路：
挨著比較鏈表1和鏈表2蔬崩。
要注意兩個(gè)鏈表都為空恶座、或其中一個(gè)鏈表為空的情況。時(shí)間復(fù)雜度為 O(max(len1, len2))
4-1：示意圖
步驟一：head1和head2對比舱殿，選出一個(gè)較小的奥裸，放入新鏈表
步驟二：head1和head2對比，選出一個(gè)較小的沪袭，放入新鏈表
步驟三：head1和head2對比湾宙，選出一個(gè)較小的樟氢，放入新鏈表
步驟四：head1和head2對比贷痪，選出一個(gè)較小的愿卸，放入新鏈表
步驟五：head1和head2對比，選出一個(gè)較小的奸笤，放入新鏈表
如此類推伟恶，temp在鏈表1和鏈表2之間移動碴开，選出較小的節(jié)點(diǎn)，放到新鏈表的后面博秫。
4-2：代碼實(shí)現(xiàn)
節(jié)點(diǎn)類：NumberNode.java
public class NumberNode {
Integer element; // 數(shù)據(jù)域
NumberNode next; // 地址域
// 節(jié)點(diǎn)的構(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é)點(diǎn)
private NumberNode headNode;
// 用來遍歷鏈表的臨時(shí)節(jié)點(diǎn)
private NumberNode tempNode;
// Getter
public NumberNode getHeadNode() {
return headNode;
}
// Setter
public void setHeadNode(NumberNode headNode) {
this.headNode = headNode;
}
// 鏈表的初始化方法
public MyNumberLinkedList() {
// 初始化時(shí)潦牛，鏈表里面只有1個(gè)節(jié)點(diǎn)，所以這個(gè)節(jié)點(diǎn)的地址域?yàn)閚ull
NumberNode node = new NumberNode(0, null);
// 頭節(jié)點(diǎn)不存儲數(shù)據(jù)挡育，它的數(shù)據(jù)域?yàn)閚ull巴碗，它的地址域存儲了第1個(gè)節(jié)點(diǎn)的地址
headNode = new NumberNode(null, node);
}
/**
* 1、插入節(jié)點(diǎn)：時(shí)間復(fù)雜度為O(n)
* @param newNode 需要插入的新節(jié)點(diǎn)
* @param position 這個(gè)變量的范圍可以從0到鏈表的長度即寒，注意不要越界橡淆。
* 頭節(jié)點(diǎn)不算進(jìn)鏈表的長度，
* 所以從頭節(jié)點(diǎn)后面的節(jié)點(diǎn)開始算起母赵，position為0
*/
public void insert(NumberNode newNode, int position) {
// 通過position變量逸爵，讓tempNode節(jié)點(diǎn)從頭節(jié)點(diǎn)開始遍歷，移動到要插入位置的前一個(gè)位置
tempNode = headNode;
int i = 0;
while (i < position) {
tempNode = tempNode.next;
i++;
}
newNode.next = tempNode.next;
tempNode.next = newNode;
}
/**
* 2凹嘲、刪除節(jié)點(diǎn)：時(shí)間復(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é)點(diǎn)：時(shí)間復(fù)雜度為O(n)
* @param position
* @return 返回查找的節(jié)點(diǎn)
*/
public NumberNode find(int position) {
// 這里同樣需要用tempNode從頭開始向后查找position
tempNode = headNode;
int i = 0;
while (i < position) {
tempNode = tempNode.next;
i++;
}
return tempNode.next;
}
/**
* 4、獲取鏈表的長度：時(shí)間復(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的地址域?yàn)閚ull時(shí)周蹭，size記得加上最后一個(gè)節(jié)點(diǎn)
return size;
}
// 遍歷鏈表溯革，打印出所有節(jié)點(diǎn)的方法
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 {
/**
* 合并兩個(gè)有序鏈表，使合并之后的鏈表依然有序
*
* @param head1 有序鏈表1的第一個(gè)有效節(jié)點(diǎn)(注意與頭節(jié)點(diǎn)的區(qū)分谷醉！)
* @param head2 有序鏈表2的第一個(gè)有效節(jié)點(diǎn)(注意與頭節(jié)點(diǎn)的區(qū)分致稀！)
* @return 返回合并好的有序鏈表的第一個(gè)有效節(jié)點(diǎn)(注意與頭節(jié)點(diǎn)的區(qū)分！)
* @throws Exception
*/
public NumberNode mergeLinkedList(NumberNode head1, NumberNode head2) throws Exception {
// 如果兩個(gè)鏈表都為空
if (head1 == null && head2 == null) {
throw new Exception("兩個(gè)鏈表都為空");
}
if (head1 == null) {
return head2;
}
if (head2 == null) {
return head1;
}
// 新鏈表的第一個(gè)有效節(jié)點(diǎn)(注意與頭節(jié)點(diǎn)的區(qū)分俱尼！)
NumberNode newHead;
// temp指針會在兩個(gè)鏈表中來回選出較小的節(jié)點(diǎn)
NumberNode temp;
// 一開始抖单，讓temp指針指向head1和head2中較小的數(shù)據(jù)，得到head節(jié)點(diǎn)
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指針的下一個(gè)節(jié)點(diǎn)對應(yīng)較小的那個(gè)數(shù)據(jù)
temp.setNext(head1);
// temp指針往后移
temp = temp.getNext();
// head1也要往后移
head1 = head1.getNext();
} else {
temp.setNext(head2);
temp = temp.getNext();
head2 = head2.getNext();
}
}
// 合并剩下的節(jié)點(diǎn)遇八，剩下的節(jié)點(diǎn)一定是都在同一個(gè)鏈表中
// 如果head1不為空矛绘，說明鏈表1里面還有節(jié)點(diǎn)，鏈表2已經(jīng)被遍歷完了
if (head1 != null) {
temp.setNext(head1);
}
if (head2 != null) {
temp.setNext(head2);
}
// 返回新鏈表的第一個(gè)有效節(jié)點(diǎn)(注意與頭節(jié)點(diǎn)的區(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货矮、找出兩個(gè)單向鏈表相交的第一個(gè)公共節(jié)點(diǎn)
5-1：示意圖
兩個(gè)節(jié)點(diǎn)相交的第一個(gè)公共節(jié)點(diǎn)如下圖：
5-2：思路
方法一：
面試時(shí)，很多人碰到這道題的第一反應(yīng)是：在第一個(gè)鏈表上順序遍歷每個(gè)節(jié)點(diǎn)斯够，每遍歷到一個(gè)節(jié)點(diǎn)的時(shí)候囚玫，在第二個(gè)鏈表上順序遍歷每個(gè)節(jié)點(diǎn)喧锦。如果在第二個(gè)鏈表上有一個(gè)節(jié)點(diǎn)和第一個(gè)鏈表上的節(jié)點(diǎn)一樣，說明兩個(gè)鏈表在這個(gè)節(jié)點(diǎn)上重合抓督。所以這種方法的時(shí)間復(fù)雜度為 O(len1 * len2)
方法二：（用棧）
參考上面的示意圖燃少，如果兩個(gè)鏈表有公共節(jié)點(diǎn)，那么最后一個(gè)節(jié)點(diǎn)（節(jié)點(diǎn)7）一定是一樣的铃在，而且是從中間的某一個(gè)節(jié)點(diǎn)（節(jié)點(diǎn)6）開始阵具，后面的節(jié)點(diǎn)都是一樣的。
現(xiàn)在的問題是定铜，在單鏈表中阳液，我們只能從頭節(jié)點(diǎn)開始順序遍歷，最后才能到達(dá)尾節(jié)點(diǎn)揣炕。最后到達(dá)的尾節(jié)點(diǎn)卻要先被比較趁舀，這聽起來是不是像“先進(jìn)后出”？于是我們就能想到利用棧來解決這個(gè)問題：分別把兩個(gè)鏈表的節(jié)點(diǎn)放入兩個(gè)棧中祝沸，這樣兩個(gè)鏈表的尾節(jié)點(diǎn)就位于兩個(gè)棧的棧頂，接下來從兩個(gè)棧的棧頂開始比較越庇，直到找到最后一個(gè)相同的節(jié)點(diǎn)罩锐，就是他們的公共點(diǎn)。
這種方法中卤唉，我們需要利用兩個(gè)輔助棧涩惑，空間復(fù)雜度是 O(len1+len2)，時(shí)間復(fù)雜度是 O(len1+len2)桑驱。跟方法一相比竭恬，時(shí)間效率得到了提高，相當(dāng)于利用空間來換取時(shí)間熬的。
那么痊硕，有沒有更好的方法呢？接下來要講押框。
方法三：（快慢指針）****
其實(shí)我們還有一個(gè)更簡單的方法：首先遍歷兩個(gè)鏈表得到它們的長度岔绸。在第二次遍歷的時(shí)候，在較長的鏈表上走 |len1-len2| 步橡伞，然后再同時(shí)遍歷這兩個(gè)鏈表盒揉，找到的第一個(gè)相同的節(jié)點(diǎn)就是它們的第一個(gè)公共點(diǎn)。
這種方法的時(shí)間復(fù)雜度也是 O(len1+len2)兑徘，但是我們不再需要用兩個(gè)棧刚盈，因此提高了空間效率。當(dāng)面試官肯定了我們的最后一種思路的時(shí)候挂脑，就可以動手寫代碼了藕漱。
5-3：代碼
這里我只寫方法三的實(shí)現(xiàn)代碼：
QuestionFiveDemo.java
import org.junit.Test;
public class QuestionFiveDemo {
/**
* 方法：求兩個(gè)鏈表相交的第一個(gè)公共節(jié)點(diǎn)
*
* @param head1 鏈表1頭節(jié)點(diǎn)后面的第一個(gè)節(jié)點(diǎn)
* @param head2 鏈表2頭節(jié)點(diǎn)后面的第一個(gè)節(jié)點(diǎn)
* @return 返回兩個(gè)鏈表的第一個(gè)公共節(jié)點(diǎn)
*/
public NumberNode getFirstCommonNode(NumberNode head1, NumberNode head2) {
if (head1 == null || head2 == null) {
return null;
}
int size1 = getSize(head1);
int size2 = getSize(head2);
// 兩個(gè)鏈表長度的差值
int diffSize = 0;
NumberNode longHead;
NumberNode shortHead;
// 找出較長的那個(gè)鏈表
if (size1 > size2) {
longHead = head1;
shortHead = head2;
diffSize = size1 - size2;
} else {
longHead = head2;
shortHead = head1;
diffSize = size2 - size1;
}
// 把較長的那個(gè)鏈表的指針向后移動diffSize個(gè)位置
for (int i = 0; i < diffSize; i++) {
longHead = longHead.getNext();
}
// 兩個(gè)鏈表的指針同時(shí)向后移動
while (longHead != null && shortHead != null) {
// 第一個(gè)相同的節(jié)點(diǎn)就是它們的公共節(jié)點(diǎn)
if (longHead.getElement() == shortHead.getElement()) {
return longHead;
}
longHead = longHead.getNext();
shortHead = shortHead.getNext();
}
return null;
}
/**
* 方法：獲取鏈表的長度
*
* @param head 指頭節(jié)點(diǎn)后面的第一個(gè)節(jié)點(diǎn)
* @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("");
// 輸出第一個(gè)公共節(jié)點(diǎn)
NumberNode commonNode = getFirstCommonNode(node1_1, node2_4);
System.out.println("第一個(gè)公共節(jié)點(diǎn)是：" + commonNode.getElement());
}
}
測試結(jié)果：
