數(shù)據(jù)是基礎(chǔ)，算法是靈魂
版權(quán)聲明，本文來(lái)自門(mén)心叼龍的博客，屬于原創(chuàng)內(nèi)容，轉(zhuǎn)載請(qǐng)注明出處。https://blog.csdn.net/geduo_83/article/details/86466640
源碼下載地址：https://download.csdn.net/download/geduo_83/10913510
初級(jí)篇：Java數(shù)據(jù)結(jié)構(gòu)與算法初級(jí)篇之?dāng)?shù)組、集合和散列表
中級(jí)篇：Java數(shù)據(jù)結(jié)構(gòu)與算法中級(jí)篇之棧、隊(duì)列、鏈表
高級(jí)篇：Java數(shù)據(jù)結(jié)構(gòu)與算法高級(jí)篇之樹(shù)、圖
理論篇：Java數(shù)組、集合、散列表常見(jiàn)算法淺析
理論篇：Java棧、隊(duì)列、鏈表常見(jiàn)算法淺析
理論篇：Java樹(shù)、圖常見(jiàn)算法淺析
****1. 概述** **
****2. 棧****
2.1 什么是棧
2.2 棧的存儲(chǔ)結(jié)構(gòu)
2.3 棧的實(shí)現(xiàn)
2.4 棧的特點(diǎn)
2.5 適用場(chǎng)景
****3. 隊(duì)列
****3.1 什么是隊(duì)列
3.2 隊(duì)列的存儲(chǔ)結(jié)構(gòu)
3.3 隊(duì)列的實(shí)現(xiàn)
3.4 隊(duì)列的特點(diǎn)
3.5 適用場(chǎng)景
**4. 鏈表
**4.1 什么是鏈表
4.2 鏈表的數(shù)據(jù)結(jié)構(gòu)
4.3 鏈表的特點(diǎn) 4.4 使用場(chǎng)景
4.5 相關(guān)算法
****1. 概述****
在上一篇文章我們講了數(shù)組、集合、散列表，接下來(lái)我們來(lái)學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)中非常有意思的幾個(gè)數(shù)據(jù)結(jié)構(gòu)--棧、隊(duì)列和鏈表，這三個(gè)結(jié)構(gòu)都有一個(gè)共同的特點(diǎn)都是順序存儲(chǔ)數(shù)據(jù)的，但是他們存儲(chǔ)數(shù)據(jù)的方式不同，各有各的特點(diǎn)，如果我們把上一篇文章學(xué)習(xí)的數(shù)組作為數(shù)據(jù)結(jié)構(gòu)中幼兒園級(jí)別的內(nèi)容，那么今天這篇文章講的這三個(gè)數(shù)據(jù)結(jié)構(gòu)相當(dāng)于小學(xué)級(jí)別的內(nèi)容了。這三種數(shù)據(jù)結(jié)構(gòu)也是我們面試的時(shí)候經(jīng)常被問(wèn)到的知識(shí)點(diǎn)。
****2. 棧****
****2.1 什么是棧****
棧是一種只能在一端進(jìn)行插入和刪除的線性數(shù)據(jù)結(jié)構(gòu)。
****2.2 棧的存儲(chǔ)結(jié)構(gòu)****
[圖片上傳失敗...(image-e253e2-1553423942540)]
?
****2.3 棧的實(shí)現(xiàn)****
我們知道數(shù)組是一切數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)，其他的大部分?jǐn)?shù)據(jù)結(jié)構(gòu)都是在數(shù)組的基礎(chǔ)上實(shí)現(xiàn)的，例如上一篇我們講過(guò)的集合，散列表，以及這一篇我們即將講到的棧和隊(duì)列。
棧的主要特點(diǎn)就是只能在一端進(jìn)行數(shù)據(jù)添加和刪除操作的數(shù)據(jù)結(jié)構(gòu)，它和集合一樣離不開(kāi)兩個(gè)最基本的操作添加和刪除，也就是數(shù)據(jù)的入棧和出棧，通過(guò)一個(gè)指針來(lái)記錄當(dāng)前下標(biāo)，入棧就是給下標(biāo)為size++的這個(gè)元素賦值，注意一點(diǎn)當(dāng)size和源數(shù)組的長(zhǎng)度相等的時(shí)候就給源數(shù)組進(jìn)行擴(kuò)容。出棧就是取出size--這個(gè)元素的值，取出之后要給size--這個(gè)位置的元素賦值為0。
package D棧隊(duì)列.A001用數(shù)組實(shí)現(xiàn)一個(gè)棧;
import java.util.Arrays;
/**
* Description: <><br>
* Author: 門(mén)心叼龍<br>
* Date: 2018/11/19<br>
* Version: V1.0.0<br>
* Update: <br>
*/
public class MyStack {
private int[] arr;
private int size = 0;
private int initsize = 5;
public MyStack() {
arr = new int[initsize];
}
public void push(int value) {
if (size == arr.length) {
arr = Arrays.copyOf(arr, size * 2);
}
arr[size++] = value;
}
public int pop() {
if (size == 0) {
throw new IndexOutOfBoundsException("棧里面數(shù)組為空了");
}
return arr[--size];
}
public int size() {
return size;
}
}
****2.4 棧的特點(diǎn)****
棧的特點(diǎn)是顯而易見(jiàn)的，只能在一端進(jìn)行操作，遵循先進(jìn)后出或者后進(jìn)先出的原則。
****2.5 適用場(chǎng)景****
****2.5.1 逆序輸出****
由于棧有先進(jìn)后出的特點(diǎn)，所以逆序輸出是其中一個(gè)非常簡(jiǎn)單的應(yīng)用。首先把要存儲(chǔ)的元素按順序入棧，然后把所有的元素都出棧，輕松實(shí)現(xiàn)逆序輸出。
****2.5.2 進(jìn)制轉(zhuǎn)換****
我們可以通過(guò)求余法，將十進(jìn)制轉(zhuǎn)化為其它進(jìn)制，比如要轉(zhuǎn)為二進(jìn)制，把十進(jìn)制數(shù)除以2，記錄余數(shù)0入棧，然后繼續(xù)將商除以2，記錄余數(shù)1入棧，一直商等于0為止，最后余數(shù)倒著寫(xiě)過(guò)來(lái)就行了。
[圖片上傳失敗...(image-c1c245-1553423942540)]
?
****2.5.3 方法棧****
函數(shù)調(diào)用的過(guò)程就是不斷的壓棧的過(guò)程，當(dāng)函數(shù)返回結(jié)果的時(shí)候就是不斷的彈棧的過(guò)程。
[圖片上傳失敗...(image-976589-1553423942540)]
?
****2.5.4 Activity棧****
做過(guò)Android開(kāi)發(fā)的同學(xué)都知道Activity的打開(kāi)就是一個(gè)不斷壓棧的過(guò)程，當(dāng)我們點(diǎn)擊返回鍵的時(shí)候就是一個(gè)不斷彈棧的過(guò)程。
[圖片上傳失敗...(image-60527d-1553423942540)]
?
****3. 隊(duì)列****
****3.1 什么是隊(duì)列****
隊(duì)列是一種只能在一端進(jìn)行插入和在另一端刪除的線性數(shù)據(jù)結(jié)構(gòu)。
****3.2 隊(duì)列的存儲(chǔ)結(jié)構(gòu)****
[圖片上傳失敗...(image-b62fb0-1553423942540)]
?
****3.3 隊(duì)列的實(shí)現(xiàn)****
棧是入棧、出棧的操作，隊(duì)列的是入列、出列的操作，我們要實(shí)現(xiàn)的是一個(gè)循環(huán)隊(duì)列，聲明兩個(gè)指針，一個(gè)頭指針，一個(gè)尾指針，頭指針用于數(shù)據(jù)的入列操作，尾指針用于數(shù)據(jù)的出列操作。
我們先來(lái)分析入列，入列數(shù)據(jù)能一直加下去嗎？不可能的，他是一個(gè)循環(huán)隊(duì)列肯定有加滿的時(shí)候，什么時(shí)候滿了？當(dāng)對(duì)頭指針加1和數(shù)組長(zhǎng)度取余如果到了尾指針的位置，那么就說(shuō)明隊(duì)列滿了就直接返回了，否則就給頭指針的元素賦值，賦值完畢一定要注意頭指針要往前挪動(dòng)一個(gè)位置。因?yàn)槭茄h(huán)隊(duì)列所以移動(dòng)指針就不是i++那么簡(jiǎn)單了，而是源指針＋1和數(shù)組長(zhǎng)度取余。
分析完了數(shù)據(jù)入列，數(shù)據(jù)出列就簡(jiǎn)單的多了，直接返回尾指針?biāo)赶虻臄?shù)組元素即可，出列注意一點(diǎn)何時(shí)隊(duì)列空了？其實(shí)很簡(jiǎn)單只要頭指針和尾指針相等了就說(shuō)明隊(duì)列已經(jīng)沒(méi)有數(shù)據(jù)了。尾指針移動(dòng)的邏輯和頭指針一樣這里就不在贅述了。
package D棧隊(duì)列.A002用數(shù)組實(shí)現(xiàn)一個(gè)隊(duì)列;
/**
* Description: <><br>
* Author: 門(mén)心叼龍<br>
* Date: 2018/11/19<br>
* Version: V1.0.0<br>
* Update: <br>
*/
public class MyQueue {
private int head = 0;
private int tail = 0;
private final int[] arr;
public MyQueue() {
arr = new int[5];
}
// 塞數(shù)據(jù)
public boolean put(int value) {
if (head == (tail + 1) % arr.length) {
System.out.println("隊(duì)列已經(jīng)滿了...");
return false;
}
arr[tail] = value;
tail = (tail + 1) % arr.length;
return true;
}
public int poll() {
if (head == tail) {
System.out.println("隊(duì)列已經(jīng)空了");
return -1;
}
int item = arr[head];
arr[head] = 0;
head = (head + 1) % arr.length;
return item;
}
}
****3.4 隊(duì)列的特點(diǎn)****
先進(jìn)先出或者后進(jìn)后出。
****3.5 適用場(chǎng)景****
****3.5.1 排隊(duì)****
只要和排隊(duì)有關(guān)的場(chǎng)景，都可以使用隊(duì)列的數(shù)據(jù)結(jié)構(gòu)來(lái)解決問(wèn)題。比如春節(jié)搶購(gòu)火車票、雙十一的搶購(gòu)活動(dòng)。
****3.5.2 Handler消息隊(duì)列****
做過(guò)Android開(kāi)發(fā)的都知道，Android系統(tǒng)有一個(gè)非常重要的消息隊(duì)列機(jī)制Handler，其數(shù)據(jù)結(jié)構(gòu)就是一個(gè)典型的隊(duì)列。
[圖片上傳失敗...(image-7418c3-1553423942539)]
?
****4. 鏈表****
****4.1 什么是鏈表****
鏈表是由一系列的節(jié)點(diǎn)組成的，當(dāng)前元素都持有對(duì)下家元素的引用，棧和隊(duì)列都是申請(qǐng)一段連續(xù)的內(nèi)存空間，然后進(jìn)行順序存儲(chǔ)數(shù)據(jù)，而鏈表是一種物理上非連續(xù)的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素之間的順序是通過(guò)每個(gè)元素的指針關(guān)聯(lián)的。
****4.2 鏈表的數(shù)據(jù)結(jié)構(gòu)****
[圖片上傳失敗...(image-3007fd-1553423942539)]
?
****4.3 鏈表的特點(diǎn)****
a.鏈表在對(duì)隊(duì)頭或者隊(duì)尾進(jìn)行插入或刪除的操作效率都非常高，時(shí)間復(fù)雜度都是O(1)
a.物理空間不連續(xù)，空間開(kāi)銷大。
b.查找元素需要順序查找，元素越靠后效率越低。
****4.4 使用場(chǎng)景****
鏈表的劣勢(shì)就是查找中間元素時(shí)需要遍歷，一般而言，鏈表也經(jīng)常配合其他的數(shù)據(jù)結(jié)構(gòu)一起使用，例如散列表、棧、隊(duì)列等。
****4.5 相關(guān)算法****
****4.5.1 實(shí)現(xiàn)一個(gè)鏈表****
鏈表的實(shí)現(xiàn)首先需要聲明一個(gè)節(jié)點(diǎn)對(duì)象，節(jié)點(diǎn)對(duì)象有兩個(gè)成員變量，一個(gè)是節(jié)點(diǎn)的值data，一個(gè)是下一個(gè)節(jié)點(diǎn)Note。
另外就是我們的核心對(duì)象鏈表對(duì)象，想一想他都有哪些成員變量？要遍歷離不開(kāi)頭節(jié)點(diǎn)，要添加一個(gè)新元素離不開(kāi)尾節(jié)點(diǎn)，另外我們有時(shí)候需要獲取一下鏈表的長(zhǎng)度，分析到這里很顯然構(gòu)成鏈表對(duì)象有三個(gè)基本的成員變量，頭節(jié)點(diǎn)，尾節(jié)點(diǎn)，長(zhǎng)度size。為了簡(jiǎn)單起見(jiàn)我我們就實(shí)現(xiàn)它的一個(gè)核心方法添加方法，當(dāng)在添加一個(gè)新節(jié)點(diǎn)的時(shí)候，首先需要建立一個(gè)Note，接著要建立鏈接關(guān)系，如果頭節(jié)點(diǎn)為空？說(shuō)明是頭一次添加則給頭節(jié)點(diǎn)賦值，否則把當(dāng)前節(jié)點(diǎn)賦值給尾節(jié)點(diǎn)的下家元素，最后一步把當(dāng)前節(jié)點(diǎn)賦值給尾結(jié)點(diǎn)就ok了。核心邏輯就是頭次給頭節(jié)點(diǎn)賦值，以后都是當(dāng)前節(jié)點(diǎn)賦值給尾結(jié)點(diǎn)的下家節(jié)點(diǎn)，并把當(dāng)前節(jié)點(diǎn)賦值給尾結(jié)點(diǎn)。不要忘了每次添加一個(gè)新的元素都需要給size加1，這樣一個(gè)簡(jiǎn)單的鏈表就實(shí)現(xiàn)了，另外需要提供一個(gè)返回頭結(jié)點(diǎn)的方法以便我們對(duì)鏈表進(jìn)行遍歷等操作。
ListNote.java:
package E鏈表.A001實(shí)現(xiàn)一個(gè)鏈表;
/**
* Description: <><br>
* Author: 門(mén)心叼龍<br>
* Date: 2018/11/19<br>
* Version: V1.0.0<br>
* Update: <br>
*/
public class ListNode {
public int data;
public ListNode next;
public ListNode(int val) {
this.data = val;
}
public ListNode() {
this.data = data;
}
public void setNext(ListNode next) {
this.next = next;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public ListNode getNext() {
return next;
}
}
MyListLink.java:
package E鏈表.A001實(shí)現(xiàn)一個(gè)鏈表;
/**
* Description: <用數(shù)組實(shí)現(xiàn)一個(gè)鏈表><br>
* Author: 門(mén)心叼龍<br>
* Date: 2018/11/20<br>
* Version: V1.0.0<br>
* Update: <br>
*/
public class MyListLink {
private ListNode first;
private ListNode last;
private int size;
public void addLast(int value) {
ListNode listNote = new ListNode();
listNote.setData(value);
if (first == null) {
first = listNote;
} else {
last.setNext(listNote);
}
last = listNote;
size++;
}
public ListNode getListLink() {
return first;
}
}
MainAlgorithm.java
package E鏈表.A001實(shí)現(xiàn)一個(gè)鏈表;
/**
* Description: <用數(shù)組實(shí)現(xiàn)一個(gè)鏈表><br>
* Author: 門(mén)心叼龍<br>
* Date: 2018/11/21<br>
* Version: V1.0.0<br>
* Update: <br>
*/
public class MainAlgorithm {
public static void main(String[] args) {
MyListLink listLink = new MyListLink();
listLink.addLast(1);
listLink.addLast(3);
listLink.addLast(2);
listLink.addLast(11);
ListNode headnode = listLink.getListLink();
while (headnode != null) {
System.out.println(headnode.data);
headnode = headnode.next;
}
}
}
****4.5.2 檢查鏈表有沒(méi)有環(huán)****
法1，計(jì)數(shù)法，原理和我們上一篇文章講過(guò)的判斷一個(gè)數(shù)組里面有沒(méi)有重復(fù)元素的道理是一樣的，遍歷鏈表中的每一個(gè)元素，如果沒(méi)有就往Set集合里面塞，有就直接返回了。
法2，差速法，聲明兩個(gè)指針，一個(gè)快指針，一個(gè)慢指針。遍歷鏈表，快指針一次走兩步，慢指針一次走一步，有環(huán)則必回相遇。鏈表遍歷的結(jié)束條件需要注意一下，快節(jié)點(diǎn)不為空且快節(jié)點(diǎn)的下家節(jié)點(diǎn)也不為空。
package E鏈表.A002檢查鏈表有沒(méi)有環(huán);
import java.util.HashSet;
import E鏈表.A001實(shí)現(xiàn)一個(gè)鏈表.ListNode;
/**
* Description: <檢查鏈表有沒(méi)有環(huán)><br>
* Author: 門(mén)心叼龍<br>
* Date: 2018/11/21<br>
* Version: V1.0.0<br>
* Update: <br>
*/
public class MainAgorithm {
public static void main(String[] args) {
ListNode listNote = new ListNode(0);
ListNode listNote1 = new ListNode(1);
ListNode listNote2 = new ListNode(2);
ListNode listNote3 = new ListNode(3);
listNote.setNext(listNote1);
listNote1.setNext(listNote2);
listNote2.setNext(listNote3);
listNote3.setNext(listNote1);
boolean loop = checkLoop(listNote);
System.out.println(loop);
}
// 計(jì)數(shù)法
public static boolean checkLoop1(ListNode listNote) {
HashSet<ListNode> hashSet = new HashSet<>();
ListNode temp = listNote;
while (temp != null) {
if (hashSet.contains(temp)) {
return true;
} else {
hashSet.add(temp);
}
temp = temp.next;
}
return false;
}
// 差速發(fā)
private static boolean checkLoop(ListNode listNote) {
ListNode slow = listNote;
ListNode fast = listNote;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
// 只要有環(huán)必然會(huì)相遇
if (fast == slow) {
return true;
}
}
return false;
}
}
****4.5.3 查找有環(huán)鏈表的入口節(jié)點(diǎn)****
其實(shí)查找鏈表入口節(jié)點(diǎn)的算法是在判斷一個(gè)鏈表有沒(méi)有環(huán)的算法差速法的基礎(chǔ)上實(shí)現(xiàn)的，如果發(fā)現(xiàn)有環(huán)則退出循環(huán)，接著慢節(jié)點(diǎn)回到頭節(jié)點(diǎn)，然后快節(jié)點(diǎn)和慢節(jié)點(diǎn)一直往前移動(dòng)下去，要注意此時(shí)快節(jié)點(diǎn)和慢節(jié)點(diǎn)都是一次挪動(dòng)一個(gè)位置，若相遇則退出循環(huán)，此時(shí)的慢節(jié)點(diǎn)就是我們所要查找的入口節(jié)點(diǎn)。
為什么這樣操作就能找到入口節(jié)點(diǎn)？因?yàn)檫@里面存在一個(gè)非常重要的原理，就是從頭節(jié)點(diǎn)到入口節(jié)點(diǎn)的距離等于從相遇節(jié)點(diǎn)到入口節(jié)點(diǎn)的距離，為什么是這樣的，我們來(lái)推導(dǎo)一下，我們知道慢指針一次走一步，快指針一次走兩步，初始快指針和慢指針都在頭節(jié)點(diǎn)s0，f0，我們開(kāi)始移動(dòng)指針s1,f2 ; s2,f4 ; s3,f6…因此我們得出一個(gè)結(jié)論，快指針?biāo)叩木嚯x始終是慢指針距離的2倍，那么如果設(shè)頭節(jié)點(diǎn)到入口節(jié)點(diǎn)的距離為m，從入口節(jié)點(diǎn)到相遇節(jié)點(diǎn)的距離為x，從相遇節(jié)點(diǎn)到入口節(jié)點(diǎn)的距離為y，那么當(dāng)快慢節(jié)點(diǎn)相遇時(shí)則有2倍的慢節(jié)點(diǎn)走的距離等于快節(jié)點(diǎn)所走的距離，即就是:2(m+x) = m + x + y + x ; 也就是: 2m + 2x = m + 2x + y ;即可得: m = y;所以當(dāng)慢節(jié)點(diǎn)再次回退到頭節(jié)點(diǎn)和快節(jié)點(diǎn)同時(shí)開(kāi)始移動(dòng)時(shí)，注意了此時(shí)快節(jié)點(diǎn)一次移動(dòng)一個(gè)節(jié)點(diǎn)，那么再次相遇的節(jié)點(diǎn)就是循環(huán)鏈表的入口節(jié)點(diǎn)。
package E鏈表.A003查找有環(huán)鏈表的入口節(jié)點(diǎn);
import E鏈表.A001實(shí)現(xiàn)一個(gè)鏈表.ListNode;
/**
* Description: <查找有環(huán)鏈表的入口節(jié)點(diǎn)><br>
* Author: 門(mén)心叼龍<br>
* Date: 2018/11/21<br>
* Version: V1.0.0<br>
* Update: <br>
*/
public class MainAgorithm {
public static void main(String[] args) {
ListNode listNote = new ListNode(0);
ListNode listNote1 = new ListNode(1);
ListNode listNote2 = new ListNode(2);
ListNode listNote3 = new ListNode(3);
listNote.setNext(listNote1);
listNote1.setNext(listNote2);
listNote2.setNext(listNote3);
listNote3.setNext(listNote1);
ListNode firstNode = getFirstNode(listNote);
System.out.println(firstNode.data);
}
// 查找有環(huán)鏈表的入口節(jié)點(diǎn)
private static ListNode getFirstNode(ListNode listNote) {
// 如果鏈表有環(huán)，請(qǐng)找到其入口節(jié)點(diǎn)
ListNode slow = listNote;
ListNode fast = listNote;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
break;
}
}
if (fast == null || fast.next == null) {
return null;
}
// 重置slow指針
slow = listNote;
// 如果沒(méi)有相遇則繼續(xù)往下走
// 定理:從頭結(jié)點(diǎn)到入口節(jié)點(diǎn)的距離等于從相遇節(jié)點(diǎn)到入口節(jié)點(diǎn)的距離*****
// 因?yàn)椋?(m + x) = m + x + y + x;
// 所以：2m+2x = m + 2x + y
// 得出：m = y;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
****4.5.6 翻轉(zhuǎn)一個(gè)鏈表****
這個(gè)問(wèn)題有兩種解法，法1指針?lè)?，這種方法的主要思想就是通過(guò)一個(gè)遍歷，每走一步把當(dāng)前節(jié)點(diǎn)挪動(dòng)到新鏈表的頭部即可，法2是數(shù)組法，我們主要講第二種算法，要反轉(zhuǎn)那么就要倒敘遍歷，怎么辦？對(duì)于鏈表來(lái)說(shuō)很困難，如果是一個(gè)數(shù)組就方便多了，如果我們將鏈表的元素存入數(shù)組將何如？豁然開(kāi)朗，對(duì)就先將鏈表元素存入數(shù)組，然后在倒敘遍歷這個(gè)數(shù)組，遍歷的時(shí)候?qū)⒐?jié)點(diǎn)元素依次插入新鏈表即可。注意了把最后一個(gè)節(jié)點(diǎn)的next鏈賦值為null否則會(huì)出現(xiàn)循環(huán)鏈表。
package E鏈表.A004翻轉(zhuǎn)一個(gè)鏈表;
import java.util.ArrayList;
import java.util.List;
import E鏈表.A001實(shí)現(xiàn)一個(gè)鏈表.ListNode;
import E鏈表.A001實(shí)現(xiàn)一個(gè)鏈表.MyListLink;
/**
* Description: <翻轉(zhuǎn)一個(gè)鏈表><br>
* Author: 門(mén)心叼龍<br>
* Date: 2018/11/21<br>
* Version: V1.0.0<br>
* Update: <br>
*/
public class MainAlgorithm {
public static void main(String[] args) {
MyListLink link = new MyListLink();
link.addLast(0);
link.addLast(1);
link.addLast(3);
link.addLast(6);
ListNode listNote = reverseListNode(link.getListLink());
while (listNote != null) {
System.out.println(listNote.getData());
listNote = listNote.next;
}
}
// 指針?lè)? private static ListNode reverseListNode2(ListNode listNote) {
// 聲明的頭指針
ListNode head = listNote;
// 申明一個(gè)尾指針
ListNode tail = listNote;
// 聲明一個(gè)next指針
ListNode next = listNote.next;
// 計(jì)算鏈表的長(zhǎng)度
int size = 0;
ListNode temp = listNote;
while (temp != null) {
size++;
temp = temp.next;
}
while (size > 1) {
// 緩存一個(gè)next
ListNode nextNext = next.next;
// 更改next的next指針
next.next = head;// 反向了
// 移動(dòng)head指針的指向
head = next;
// 移動(dòng)next指針的指向
next = nextNext;
size--;
}
// 此時(shí)鏈表有環(huán)，干掉環(huán)
tail.next = null;
return head;
}
// 數(shù)組法
private static ListNode reverseListNode(ListNode listNote) {
// 翻轉(zhuǎn)一個(gè)鏈表
ListNode tempNode = listNote;
// 把鏈表的值都放入List集合里面
// 通過(guò)翻轉(zhuǎn)數(shù)組來(lái)翻轉(zhuǎn)集合
List<ListNode> list = new ArrayList<>();
while (tempNode != null) {
list.add(tempNode);
tempNode = tempNode.next;
}
ListNode headNode = null;
for (int i = list.size() - 1; i >= 0; i--) {
if (headNode == null) {
headNode = new ListNode();
headNode = list.get(i);
headNode.next = list.get(i - 1);
} else {
if (i == 0) {
list.get(i).next = null;
} else {
list.get(i).next = list.get(i - 1);
}
}
}
return headNode;
}
}
****4.5.7 刪除鏈表倒數(shù)第N個(gè)節(jié)點(diǎn)****
要?jiǎng)h除倒數(shù)第n個(gè)節(jié)點(diǎn)，那么我們只要找到要?jiǎng)h除的那個(gè)節(jié)點(diǎn)前面的那個(gè)節(jié)點(diǎn)pb,然后再執(zhí)行pb.next = pb.next.next，這樣就輕松的把第n個(gè)節(jié)點(diǎn)刪除了，我們想了，要?jiǎng)h除倒數(shù)那個(gè)節(jié)點(diǎn)，我們先找到正數(shù)的那個(gè)節(jié)點(diǎn)指針pa，然后再聲明一個(gè)指向鏈表的頭部指針pb，以然后兩個(gè)指針同時(shí)移動(dòng)，直到pa移動(dòng)到最后，則此時(shí)節(jié)點(diǎn)pb就是我們要?jiǎng)h除那個(gè)節(jié)點(diǎn)的前面那個(gè)節(jié)點(diǎn)，我們?cè)賵?zhí)行pb.next = pb.next.next ，同時(shí)返回頭節(jié)點(diǎn)就ok了。
package E鏈表.A005刪除鏈表中的倒數(shù)第N個(gè)節(jié)點(diǎn);
import E鏈表.A001實(shí)現(xiàn)一個(gè)鏈表.ListNode;
import E鏈表.A001實(shí)現(xiàn)一個(gè)鏈表.MyListLink;
/**
* Description: <刪除鏈表中的倒數(shù)第N個(gè)元素><br>
* Author: 門(mén)心叼龍<br>
* Date: 2018/11/23<br>
* Version: V1.0.0<br>
* Update: <br>
*/
public class MainAlgorithm {
public static void main(String[] args){
MyListLink myListLink = new MyListLink();
myListLink.addLast(0);
myListLink.addLast(1);
myListLink.addLast(2);
myListLink.addLast(3);
myListLink.addLast(4);
//刪除倒數(shù)第2個(gè)元素
ListNode head = removeReIndex(myListLink.getListLink(), 3);
while(head != null){
System.out.println(head.data);
head = head.next;
}
}
private static ListNode removeReIndex(ListNode listNode, int n) {
ListNode head = listNode;
ListNode pb = listNode;
ListNode pa = listNode;
int i = 0;
while(i < n ){
pa = pa.next;
i++;
}
while(pa.next != null){
pa = pa.next;
pb = pb.next;
}
pb.next = pb.next.next;
return head;
}
}
****4.5.8 合并兩個(gè)有序鏈表****
簡(jiǎn)單粗暴一點(diǎn)，直接將兩個(gè)鏈表轉(zhuǎn)化為兩個(gè)數(shù)組，然后再將兩個(gè)數(shù)組合并為一個(gè)數(shù)組，然后對(duì)新數(shù)組排序，最后再將該數(shù)組轉(zhuǎn)化為一個(gè)鏈表即可解決問(wèn)題。
第二種方法通過(guò)指針?lè)?，首先聲明兩個(gè)指針，一個(gè)頭指針，一個(gè)尾指針，接著開(kāi)始遍歷兩個(gè)鏈表，每走一步比較一下當(dāng)前的兩個(gè)元素的大小，如果哪個(gè)小就把他添加到尾指針，直到循環(huán)完畢，最后一步把不為空的那個(gè)鏈表節(jié)點(diǎn)添加到尾指針的屁股后面即可。
package E鏈表.A006合并兩個(gè)排好序的鏈表;
import E鏈表.A001實(shí)現(xiàn)一個(gè)鏈表.ListNode;
import E鏈表.A001實(shí)現(xiàn)一個(gè)鏈表.MyListLink;
/**
* Description: <合并兩個(gè)排好序的鏈表><br>
* Author: 門(mén)心叼龍<br>
* Date: 2018/11/22<br>
* Version: V1.0.0<br>
* Update: <br>
*/
public class MainAlgorithm {
public static void main(String[] args) {
MyListLink myListLink = new MyListLink();
myListLink.addLast(0);
myListLink.addLast(2);
myListLink.addLast(4);
MyListLink myListLink1 = new MyListLink();
myListLink1.addLast(1);
myListLink1.addLast(3);
myListLink1.addLast(40);
myListLink1.addLast(50);
ListNode listNode = mergerListNode(myListLink.getListLink(), myListLink1.getListLink());
while (listNode != null) {
System.out.println(listNode.data);
listNode = listNode.next;
}
}
public static ListNode mergerListNode(ListNode listNode1, ListNode listNode2) {
ListNode head = new ListNode(0);
ListNode tail = head;
while (listNode1 != null && listNode2 != null) {
if (listNode1.data < listNode2.data) {
tail.next = listNode1;
listNode1 = listNode1.next;
} else {
tail.next = listNode2;
listNode2 = listNode2.next;
}
tail = tail.next;
}
tail.next = listNode1 != null ? listNode1 : listNode2;
return head.next;
}
}
源碼下載地址：https://download.csdn.net/download/geduo_83/10913510
初級(jí)篇：Java數(shù)據(jù)結(jié)構(gòu)與算法初級(jí)篇之?dāng)?shù)組、集合和散列表
中級(jí)篇：Java數(shù)據(jù)結(jié)構(gòu)與算法中級(jí)篇之棧、隊(duì)列、鏈表
高級(jí)篇：Java數(shù)據(jù)結(jié)構(gòu)與算法高級(jí)篇之樹(shù)、圖
理論篇：Java數(shù)組、集合、散列表常見(jiàn)算法淺析
理論篇：Java棧、隊(duì)列、鏈表常見(jiàn)算法淺析
理論篇：Java樹(shù)、圖常見(jiàn)算法淺析
問(wèn)題反饋
有任何問(wèn)題，請(qǐng)?jiān)谖恼孪路浇o我留言。
關(guān)于作者
var geduo_83 = {
nickName : "門(mén)心叼龍",
site : "http://www.weibo.com/geduo83"
}
