JAVA完成鏈外面試題。本站提示廣大學習愛好者：（JAVA完成鏈外面試題）文章只能為提供參考，不一定能成為您想要的結果。以下是JAVA完成鏈外面試題正文
這份筆記整頓了整整一個禮拜，每行代碼都是本身默寫完成，並測試運轉勝利，同時也回想了一下《劍指offer》這本書中和鏈表有關的講授，願望對口試和面試有所贊助。
本文包括鏈表的以下內容：
1、單鏈表的創立和遍歷
2、求單鏈表中節點的個數
3、查找單鏈表中的倒數第k個結點（劍指offer，題15）
4、查找單鏈表中的中央結點
5、歸並兩個有序的單鏈表，歸並以後的鏈表仍然有序【湧現頻率高】（劍指offer，題17）
6、單鏈表的反轉【湧現頻率最高】（劍指offer，題16）
7、從尾到頭打印單鏈表（劍指offer，題5）
8、斷定單鏈表能否有環
9、掏出有環鏈表中，環的長度
10、單鏈表中，掏出環的肇端點（劍指offer，題56）。本題需應用下面的第8題和第9題。
11、斷定兩個單鏈表訂交的第一個交點（劍指offer，題37）
1、單鏈表的創立和遍歷：
public class LinkList {
public Node head;
public Node current;
//辦法：向鏈表中添加數據
public void add(int data) {
//斷定鏈表為空的時刻
if (head == null) {//假如頭結點為空，解釋這個鏈表還沒有創立，那就把新的結點賦給頭結點
head = new Node(data);
current = head;
} else {
//創立新的結點，放在以後節點的前面（把新的結點合鏈表停止聯系關系）
current.next = new Node(data);
//把鏈表確當前索引向後挪動一名
current = current.next; //此步操作完成以後，current結點指向新添加的誰人結點
}
}
//辦法：遍歷鏈表（打印輸入鏈表。辦法的參數表現從節點node開端停止遍歷
public void print(Node node) {
if (node == null) {
return;
}
current = node;
while (current != null) {
System.out.println(current.data);
current = current.next;
}
}
class Node {
//注：此處的兩個成員變量權限不克不及為private，由於private的權限是僅對本類拜訪。
int data; //數據域
Node next;//指針域
public Node(int data) {
this.data = data;
}
}
public static void main(String[] args) {
LinkList list = new LinkList();
//向LinkList中添加數據
for (int i = 0; i < 10; i++) {
list.add(i);
}
list.print(list.head);// 從head節點開端遍歷輸入
}
}
上方代碼中，這外面的Node節點采取的是外部類來表現（33行）。應用外部類的最年夜利益是可以和內部類停止公有操作的相互拜訪。
注：外部類拜訪的特色是：外部類可以直接拜訪內部類的成員，包含公有；內部類要拜訪外部類的成員，必需先創立對象。
為了便利添加和遍歷的操作，在LinkList類中添加一個成員變量current，用來表現以後節點的索引（03行）。
這外面的遍歷鏈表的辦法（20行）中，參數node表現從node節點開端遍歷，紛歧定要從head節點遍歷。
2、求單鏈表中節點的個數：
留意檢討鏈表能否為空。時光龐雜度為O（n）。這個比擬簡略。
焦點代碼：
//辦法：獲得單鏈表的長度
public int getLength(Node head) {
if (head == null) {
return 0;
}
int length = 0;
Node current = head;
while (current != null) {
length++;
current = current.next;
}
return length;
}
3、查找單鏈表中的倒數第k個結點：
3.1 通俗思緒：
先將全部鏈表從頭至尾遍歷一次，盤算出鏈表的長度size，獲得鏈表的長度以後，就好辦了，直接輸入第(size-k)個節點便可以了（留意鏈表為空，k為0，k為1，k年夜於鏈表中節點個數時的情形
）。時光龐雜度為O（n），年夜概思緒以下：
public int findLastNode(int index) { //index代表的是倒數第index的誰人結點
//第一次遍歷，獲得鏈表的長度size
if (head == null) {
return -1;
}
current = head;
while (current != null) {
size++;
current = current.next;
}
//第二次遍歷，輸入倒數第index個結點的數據
current = head;
for (int i = 0; i < size - index; i++) {
current = current.next;
}
return current.data;
}
假如面試官不許可你遍歷鏈表的長度，該怎樣做呢？接上去就是。
3.2 改良思緒：（這類思緒在其他標題中也有運用）
這裡須要聲明兩個指針：即兩個結點型的變量first和second，起首讓first和second都指向第一個結點，然後讓second結點往後挪k-1個地位，此時first和second就距離了k-1個地位，然後全體向後挪動這兩個節點，直到second節點走到最初一個結點的時刻，此時first節點所指向的地位就是倒數第k個節點的地位。時光龐雜度為O（n）
代碼完成：（第一版）
public Node findLastNode(Node head, int index) {
if (node == null) {
return null;
}
Node first = head;
Node second = head;
//讓second結點往後挪index個地位
for (int i = 0; i < index; i++) {
second = second.next;
}
//讓first和second結點全體向後挪動，直到second結點為Null
while (second != null) {
first = first.next;
second = second.next;
}
//當second結點為空的時刻，此時first指向的結點就是我們要找的結點
return first;
}
代碼完成：（終究版）（斟酌k年夜於鏈表中結點個數時的情形時，拋出異常）
下面的代碼中，看似曾經完成了功效，其實還不敷硬朗:
要留意k等於0的情形；
假如k年夜於鏈表中節點個數時，就會報空指針異常，所以這裡須要做一下斷定。
焦點代碼以下：
public Node findLastNode(Node head, int k) {
if (k == 0 || head == null) {
return null;
}
Node first = head;
Node second = head;
//讓second結點往後挪k-1個地位
for (int i = 0; i < k - 1; i++) {
System.out.println("i的值是" + i);
second = second.next;
if (second == null) { //解釋k的值曾經年夜於鏈表的長度了
//throw new NullPointerException("鏈表的長度小於" + k); //我們本身拋出異常，給用戶以提醒
return null;
}
}
//讓first和second結點全體向後挪動，直到second走到最初一個結點
while (second.next != null) {
first = first.next;
second = second.next;
}
//當second結點走到最初一個節點的時刻，此時first指向的結點就是我們要找的結點
return first;
}
4、查找單鏈表中的中央結點：
異樣，面試官不許可你算出鏈表的長度，該怎樣做呢？
思緒：
和下面的第2節一樣，也是設置兩個指針first和second，只不外這裡是，兩個指針同時向前走，second指針每次走兩步，first指針每次走一步，直到second指針走到最初一個結點時，此時first指針所指的結點就是中央結點。留意鏈表為空，鏈表結點個數為1和2的情形。時光龐雜度為O（n）。
代碼完成：
//辦法：查找鏈表的中央結點
public Node findMidNode(Node head) {
if (head == null) {
return null;
}
Node first = head;
Node second = head;
//每次挪動時，讓second結點挪動兩位，first結點挪動一名
while (second != null && second.next != null) {
first = first.next;
second = second.next.next;
}
//直到second結點挪動到null時，此時first指針指向的地位就是中央結點的地位
return first;
}
上方代碼中，當n為偶數時，獲得的中央結點是第n/2 + 1個結點。好比鏈表有6個節點時，獲得的是第4個節點。
5、歸並兩個有序的單鏈表，歸並以後的鏈表仍然有序：
這道題常常被各公司考核。
例如：
鏈表1：
1->2->3->4
鏈表2：
2->3->4->5
歸並後：
1->2->2->3->3->4->4->5
解題思緒：
挨著比擬鏈表1和鏈表2。
這個相似於合並排序。特別要留意兩個鏈表都為空、和個中一個為空的情形。只須要O (1) 的空間。時光龐雜度為O (max(len1,len2))
代碼完成：
//兩個參數代表的是兩個鏈表的頭結點
public Node mergeLinkList(Node head1, Node head2) {
if (head1 == null && head2 == null) { //假如兩個鏈表都為空
return null;
}
if (head1 == null) {
return head2;
}
if (head2 == null) {
return head1;
}
Node head; //新鏈表的頭結點
Node current; //current結點指向新鏈表
// 一開端，我們讓current結點指向head1和head2中較小的數據，獲得head結點
if (head1.data < head2.data) {
head = head1;
current = head1;
head1 = head1.next;
} else {
head = head2;
current = head2;
head2 = head2.next;
}
while (head1 != null && head2 != null) {
if (head1.data < head2.data) {
current.next = head1; //新鏈表中，current指針的下一個結點對應較小的誰人數據
current = current.next; //current指針下移
head1 = head1.next;
} else {
current.next = head2;
current = current.next;
head2 = head2.next;
}
}
//歸並殘剩的元素
if (head1 != null) { //解釋鏈表2遍歷完了，是空的
current.next = head1;
}
if (head2 != null) { //解釋鏈表1遍歷完了，是空的
current.next = head2;
}
return head;
}
代碼測試：
public static void main(String[] args) {
LinkList list1 = new LinkList();
LinkList list2 = new LinkList();
//向LinkList中添加數據
for (int i = 0; i < 4; i++) {
list1.add(i);
}
for (int i = 3; i < 8; i++) {
list2.add(i);
}
LinkList list3 = new LinkList();
list3.head = list3.mergeLinkList(list1.head, list2.head); //將list1和list2歸並，寄存到list3中
list3.print(list3.head);// 從head節點開端遍歷輸入
}
上方代碼頂用到的add辦法和print辦法和第1末節中是分歧的。
運轉後果：
注：《劍指offer》中是用遞歸處理的，感到有點難懂得。
6、單鏈表的反轉：【湧現頻率最高】
例如鏈表：
1->2->3->4
反轉以後：
4->2->2->1
思緒：
從頭至尾遍歷原鏈表，每遍歷一個結點，將其摘下放在新鏈表的最前端。留意鏈表為空和只要一個結點的情形。時光龐雜度為O（n）
辦法1：（遍歷）
//辦法：鏈表的反轉
public Node reverseList(Node head) {
//假如鏈表為空或許只要一個節點，無需反轉，直接前往原鏈表的頭結點
if (head == null || head.next == null) {
return head;
}
Node current = head;
Node next = null; //界說以後結點的下一個結點
Node reverseHead = null; //反轉後新鏈表的表頭
while (current != null) {
next = current.next; //臨時保留住以後結點的下一個結點，由於下一主要用
current.next = reverseHead; //將current的下一個結點指向新鏈表的頭結點
reverseHead = current;
current = next; // 操作停止後，current節點後移
}
return reverseHead;
}
上方代碼中，焦點代碼是第16、17行。
辦法2：（遞歸）
這個辦法有點難，先不講了。
7、從尾到頭打印單鏈表：
關於這類倒置次序的成績，我們應當就會想到棧，落後先出。所以，這一題要末本身應用棧，要末讓體系應用棧，也就是遞歸。留意鏈表為空的情形。時光龐雜度為O（n）
注：不要想著先將單鏈表反轉，然後遍歷輸入，如許會損壞鏈表的構造，不建議。
辦法1：（本身新建一個棧）
//辦法：從尾到頭打印單鏈表
public void reversePrint(Node head) {
if (head == null) {
return;
}
Stack<Node> stack = new Stack<Node>(); //新建一個棧
Node current = head;
//將鏈表的一切結點壓棧
while (current != null) {-
stack.push(current); //將以後結點壓棧
current = current.next;
}
//將棧中的結點打印輸入便可
while (stack.size() > 0) {
System.out.println(stack.pop().data); //出棧操作
}
}
辦法2：（應用體系的棧：遞歸，代碼優雅簡練）
public void reversePrint(Node head) {
if (head == null) {
return;
}
reversePrint(head.next);
System.out.println(head.data);
}
總結：辦法2是基於遞歸完成的，戴安看起來簡練優雅，但有個成績：當鏈表很長的時刻，就會招致辦法挪用的層級很深，有能夠形成棧溢出。而辦法1的顯式用棧，是基於輪回完成的，代碼的魯棒性要更好一些。
8、斷定單鏈表能否有環：
這裡也是用到兩個指針，假如一個鏈表有環，那末用一個指針去遍歷，是永久走不到頭的。
是以，我們用兩個指針去遍歷：first指針每次走一步，second指針每次走兩步，假如first指針和second指針相遇，解釋有環。時光龐雜度為O (n)。
辦法：
//辦法：斷定單鏈表能否有環
public boolean hasCycle(Node head) {
if (head == null) {
return false;
}
Node first = head;
Node second = head;
while (second != null) {
first = first.next; //first指針走一步
second = second.next.next; second指針走兩步
if (first == second) { //一旦兩個指針相遇，解釋鏈表是有環的
return true;
}
}
return false;
}
完全版代碼：（包括測試部門）
這裡，我們還須要加一個重載的add(Node node)辦法，在創立單向輪回鏈表時要用到。
LinkList.java:
public class LinkList {
public Node head;
public Node current;
//辦法：向鏈表中添加數據
public void add(int data) {
//斷定鏈表為空的時刻
if (head == null) {//假如頭結點為空，解釋這個鏈表還沒有創立，那就把新的結點賦給頭結點
head = new Node(data);
current = head;
} else {
//創立新的結點，放在以後節點的前面（把新的結點合鏈表停止聯系關系）
current.next = new Node(data);
//把鏈表確當前索引向後挪動一名
current = current.next;
}
}
//辦法重載：向鏈表中添加結點
public void add(Node node) {
if (node == null) {
return;
}
if (head == null) {
head = node;
current = head;
} else {
current.next = node;
current = current.next;
}
}
//辦法：遍歷鏈表（打印輸入鏈表。辦法的參數表現從節點node開端停止遍歷
public void print(Node node) {
if (node == null) {
return;
}
current = node;
while (current != null) {
System.out.println(current.data);
current = current.next;
}
}
//辦法：檢測單鏈表能否有環
public boolean hasCycle(Node head) {
if (head == null) {
return false;
}
Node first = head;
Node second = head;
while (second != null) {
first = first.next; //first指針走一步
second = second.next.next; //second指針走兩步
if (first == second) { //一旦兩個指針相遇，解釋鏈表是有環的
return true;
}
}
return false;
}
class Node {
//注：此處的兩個成員變量權限不克不及為private，由於private的權限是僅對本類拜訪。
int data; //數據域
Node next;//指針域
public Node(int data) {
this.data = data;
}
}
public static void main(String[] args) {
LinkList list = new LinkList();
//向LinkList中添加數據
for (int i = 0; i < 4; i++) {
list.add(i);
}
list.add(list.head); //將頭結點添加到鏈表傍邊，因而，單鏈表就有環了。備注：此時獲得的這個環的構造，是上面的第8末節中圖1的那種構造。
System.out.println(list.hasCycle(list.head));
}
}
檢測單鏈表能否有環的代碼是第50行。
88行：我們將頭結點持續往鏈表中添加，此時單鏈表就環了。終究運轉後果為true。
假如刪失落了88行代碼，此時單鏈表沒有環，運轉後果為false。
9、掏出有環鏈表中，環的長度：
我們日常平凡碰著的有環鏈表是上面的這類：（圖1）
上圖中環的長度是4。
但有能夠也是上面的這類：（圖2）
此時，上圖中環的長度就是3了。
那怎樣求出環的長度呢？
思緒：
這外面，我們須要先應用下面的第7末節中的hasCycle辦法（斷定鏈表能否有環的誰人辦法），這個辦法的前往值是boolean型，然則如今要把這個辦法稍做修正，讓其前往值為相遇的誰人結點。然後，我們拿到這個相遇的結點就好辦了，這個結點確定是在環裡嘛，我們可讓這個結點對應的指針一向往下走，直到它回到原點，便可以算出環的長度了。
辦法：
//辦法：斷定單鏈表能否有環。前往的結點是相遇的誰人結點
public Node hasCycle(Node head) {
if (head == null) {
return null;
}
Node first = head;
Node second = head;
while (second != null) {
first = first.next;
second = second.next.next;
if (first == second) { //一旦兩個指針相遇，解釋鏈表是有環的
return first; //將相遇的誰人結點停止前往
}
}
return null;
}
//辦法：有環鏈表中，獲得環的長度。參數node代表的是相遇的誰人結點
public int getCycleLength(Node node) {
if (head == null) {
return 0;
}
Node current = node;
int length = 0;
while (current != null) {
current = current.next;
length++;
if (current == node) { //當current結點走到原點的時刻
return length;
}
}
return length;
}
完全版代碼：（包括測試部門）
public class LinkList {
public Node head;
public Node current;
public int size;
//辦法：向鏈表中添加數據
public void add(int data) {
//斷定鏈表為空的時刻
if (head == null) {//假如頭結點為空，解釋這個鏈表還沒有創立，那就把新的結點賦給頭結點
head = new Node(data);
current = head;
} else {
//創立新的結點，放在以後節點的前面（把新的結點合鏈表停止聯系關系）
current.next = new Node(data);
//把鏈表確當前索引向後挪動一名
current = current.next; //此步操作完成以後，current結點指向新添加的誰人結點
}
}
//辦法重載：向鏈表中添加結點
public void add(Node node) {
if (node == null) {
return;
}
if (head == null) {
head = node;
current = head;
} else {
current.next = node;
current = current.next;
}
}
//辦法：遍歷鏈表（打印輸入鏈表。辦法的參數表現從節點node開端停止遍歷
public void print(Node node) {
if (node == null) {
return;
}
current = node;
while (current != null) {
System.out.println(current.data);
current = current.next;
}
}
//辦法：斷定單鏈表能否有環。前往的結點是相遇的誰人結點
public Node hasCycle(Node head) {
if (head == null) {
return null;
}
Node first = head;
Node second = head;
while (second != null) {
first = first.next;
second = second.next.next;
if (first == second) { //一旦兩個指針相遇，解釋鏈表是有環的
return first; //將相遇的誰人結點停止前往
}
}
return null;
}
//辦法：有環鏈表中，獲得環的長度。參數node代表的是相遇的誰人結點
public int getCycleLength(Node node) {
if (head == null) {
return 0;
}
Node current = node;
int length = 0;
while (current != null) {
current = current.next;
length++;
if (current == node) { //當current結點走到原點的時刻
return length;
}
}
return length;
}
class Node {
//注：此處的兩個成員變量權限不克不及為private，由於private的權限是僅對本類拜訪。
int data; //數據域
Node next;//指針域
public Node(int data) {
this.data = data;
}
}
public static void main(String[] args) {
LinkList list1 = new LinkList();
Node second = null; //把第二個結點記上去
//向LinkList中添加數據
for (int i = 0; i < 4; i++) {
list1.add(i);
if (i == 1) {
second = list1.current; //把第二個結點記上去
}
}
list1.add(second); //將尾結點指向鏈表的第二個結點，因而單鏈表就有環了，備注：此時獲得的環的構造，是本節中圖2的那種構造
Node current = list1.hasCycle(list1.head); //獲得相遇的誰人結點
System.out.println("環的長度為" + list1.getCycleLength(current));
}
}
運轉後果：
假如將下面的104至122行的測試代碼改成上面如許的：（即：將圖2中的構造改成圖1中的構造）
public static void main(String[] args) {
LinkList list1 = new LinkList();
//向LinkList中添加數據
for (int i = 0; i < 4; i++) {
list1.add(i);
}
list1.add(list1.head); //將頭結點添加到鏈表傍邊（將尾結點指向頭結點），因而，單鏈表就有環了。備注：此時獲得的這個環的構造，是本節中圖1的那種構造。
Node current = list1.hasCycle(list1.head);
System.out.println("環的長度為" + list1.getCycleLength(current));
}
運轉成果：
假如把下面的代碼中的第8行刪失落，那末這個鏈表就沒有環了，因而運轉的成果為0。
10、單鏈表中，掏出環的肇端點：
我們日常平凡碰著的有環鏈表是上面的這類：（圖1）
上圖中環的肇端點1。
但有能夠也是上面的這類：（圖2）
此時，上圖中環的肇端點是2。
辦法1：
這裡我們須要應用到下面第8末節的掏出環的長度的辦法getCycleLength，用這個辦法來獲得環的長度length。拿到環的長度length以後，須要用到兩個指針變量first和second，先讓second指針走length步；然後讓first指針和second指針同時各走一步，當兩個指針相遇時，相遇時的結點就是環的肇端點。
注：為了找到環的肇端點，我們須要先獲得環的長度，而為了獲得環的長度，我們須要先斷定能否有環。所以這外面實際上是用到了三個辦法。
代碼完成：
辦法1的焦點代碼：
//辦法：獲得環的肇端點。參數length表現環的長度
public Node getCycleStart(Node head, int cycleLength) {
if (head == null) {
return null;
}
Node first = head;
Node second = head;
//先讓second指針走length步
for (int i = 0; i < cycleLength; i++) {
second = second.next;
}
//然後讓first指針和second指針同時各走一步
while (first != null && second != null) {
first = first.next;
second = second.next;
if (first == second) { //假如兩個指針相遇了，解釋這個結點就是環的肇端點
return first;
}
}
return null;
}
完全版代碼：（含測試部門）
public class LinkList {
public Node head;
public Node current;
public int size;
//辦法：向鏈表中添加數據
public void add(int data) {
//斷定鏈表為空的時刻
if (head == null) {//假如頭結點為空，解釋這個鏈表還沒有創立，那就把新的結點賦給頭結點
head = new Node(data);
current = head;
} else {
//創立新的結點，放在以後節點的前面（把新的結點合鏈表停止聯系關系）
current.next = new Node(data);
//把鏈表確當前索引向後挪動一名
current = current.next; //此步操作完成以後，current結點指向新添加的誰人結點
}
}
//辦法重載：向鏈表中添加結點
public void add(Node node) {
if (node == null) {
return;
}
if (head == null) {
head = node;
current = head;
} else {
current.next = node;
current = current.next;
}
}
//辦法：遍歷鏈表（打印輸入鏈表。辦法的參數表現從節點node開端停止遍歷
public void print(Node node) {
if (node == null) {
return;
}
current = node;
while (current != null) {
System.out.println(current.data);
current = current.next;
}
}
//辦法：斷定單鏈表能否有環。前往的結點是相遇的誰人結點
public Node hasCycle(Node head) {
if (head == null) {
return null;
}
Node first = head;
Node second = head;
while (second != null) {
first = first.next;
second = second.next.next;
if (first == second) { //一旦兩個指針相遇，解釋鏈表是有環的
return first; //將相遇的誰人結點停止前往
}
}
return null;
}
//辦法：有環鏈表中，獲得環的長度。參數node代表的是相遇的誰人結點
public int getCycleLength(Node node) {
if (head == null) {
return 0;
}
Node current = node;
int length = 0;
while (current != null) {
current = current.next;
length++;
if (current == node) { //當current結點走到原點的時刻
return length;
}
}
return length;
}
//辦法：獲得環的肇端點。參數length表現環的長度
public Node getCycleStart(Node head, int cycleLength) {
if (head == null) {
return null;
}
Node first = head;
Node second = head;
//先讓second指針走length步
for (int i = 0; i < cycleLength; i++) {
second = second.next;
}
//然後讓first指針和second指針同時各走一步
while (first != null && second != null) {
first = first.next;
second = second.next;
if (first == second) { //假如兩個指針相遇了，解釋這個結點就是環的肇端點
return first;
}
}
return null;
}
class Node {
//注：此處的兩個成員變量權限不克不及為private，由於private的權限是僅對本類拜訪。
int data; //數據域
Node next;//指針域
public Node(int data) {
this.data = data;
}
}
public static void main(String[] args) {
LinkList list1 = new LinkList();
Node second = null; //把第二個結點記上去
//向LinkList中添加數據
for (int i = 0; i < 4; i++) {
list1.add(i);
if (i == 1) {
second = list1.current; //把第二個結點記上去
}
}
list1.add(second); //將尾結點指向鏈表的第二個結點，因而單鏈表就有環了，備注：此時獲得的環的構造，是本節中圖2的那種構造
Node current = list1.hasCycle(list1.head); //獲得相遇的誰人結點
int length = list1.getCycleLength(current); //獲得環的長度
System.out.println("環的肇端點是" + list1.getCycleStart(list1.head, length).data);
}
}
11、斷定兩個單鏈表訂交的第一個交點：
《編程之美》P193，5.3，面試題37就有這道題。
面試時，許多人碰著這道題的第一反響是：在第一個鏈表上次序遍歷每一個結點，每遍歷到一個結點的時刻，在第二個鏈表上次序遍歷每一個結點。假如在第二個鏈表上有一個結點和第一個鏈表上的結點一樣，解釋兩個鏈表在這個結點上重合。明顯該辦法的時光龐雜度為O(len1 * len2)。
辦法1：采取棧的思緒
我們可以看出兩個有公共結點而部門重合的鏈表，拓撲外形看起來像一個Y，而弗成能是X型。 以下圖所示：
如上圖所示，假如單鏈表有公共結點，那末最初一個結點（結點7）必定是一樣的，並且是從中央的某一個結點（結點6）開端，後續的結點都是一樣的。
如今的成績是，在單鏈表中，我們只能從頭結點開端次序遍歷，最初能力達到尾結點。最初達到的尾節點卻要先被比擬，這聽起來是否是像“先輩後出”？因而我們就可以想到應用棧的特色來處理這個成績：分離把兩個鏈表的結點放入兩個棧中，如許兩個鏈表的尾結點就位於兩個棧的棧頂，接上去比擬下一個棧頂，直到找到最初一個雷同的結點。
這類思緒中，我們須要應用兩個幫助棧，空間龐雜度是O(len1+len2)，時光龐雜度是O(len1+len2)。和一開端的蠻力法比擬，時光效力獲得了進步，相當因而應用空間消費換取時光效力。
那末，有無更好的辦法呢？接上去要講。
辦法2：斷定兩個鏈表訂交的第一個結點：用到快慢指針，推舉（更優解）
我們在下面的辦法2中，之所以用到棧，是由於我們想同時遍歷達到兩個鏈表的尾結點。其實為處理這個成績我們還有一個更簡略的方法：起首遍歷兩個鏈表獲得它們的長度。在第二次遍歷的時刻，在較長的鏈表上走 |len1-len2| 步，接著再同時在兩個鏈表上遍歷，找到的第一個雷同的結點就是它們的第一個交點。
這類思緒的時光龐雜度也是O(len1+len2)，然則我們不再須要幫助棧，是以進步了空間效力。當面試官確定了我們的最初一種思緒的時刻，便可以著手寫代碼了。
焦點代碼：
//辦法：求兩個單鏈表訂交的第一個交點
public Node getFirstCommonNode(Node head1, Node head2) {
if (head1 == null || head == null) {
return null;
}
int length1 = getLength(head1);
int length2 = getLength(head2);
int lengthDif = 0; //兩個鏈表長度的差值
Node longHead;
Node shortHead;
//找出較長的誰人鏈表
if (length1 > length2) {
longHead = head1;
shortHead = head2;
lengthDif = length1 - length2;
} else {
longHead = head2;
shortHead = head1;
lengthDif = length2 - length1;
}
//將較長的誰人鏈表的指針向前走length個間隔
for (int i = 0; i < lengthDif; i++) {
longHead = longHead.next;
}
//將兩個鏈表的指針同時向前挪動
while (longHead != null && shortHead != null) {
if (longHead == shortHead) { //第一個雷同的結點就是訂交的第一個結點
return longHead;
}
longHead = longHead.next;
shortHead = shortHead.next;
}
return null;
}
//辦法：獲得單鏈表的長度
public int getLength(Node head) {
if (head == null) {
return 0;
}
int length = 0;
Node current = head; while (current != null) {
length++;
current = current.next;
}
return length;
以上就是有關java鏈表的經典面試標題，願望可以贊助年夜家順遂經由過程面試。
