1.1 認(rèn)識(shí)鏈表
1.1.1 簡(jiǎn)介
鏈表這類數(shù)據(jù)結(jié)構(gòu)，有點(diǎn)像生活中的火車厢蒜，一節(jié)車廂連著下一節(jié)車廂，在火車?yán)锩媾胫玻挥械搅?號(hào)車廂你才能進(jìn)入5號(hào)車廂斑鸦，一般情況下，不可能直接在3號(hào)車廂繞過(guò)4號(hào)車廂進(jìn)入5號(hào)車廂草雕。不過(guò)更準(zhǔn)確來(lái)說(shuō)巷屿，火車是雙向鏈表，也就是說(shuō)在4號(hào)車廂也可以反向進(jìn)入3號(hào)車廂墩虹。
下面我們來(lái)畫(huà)個(gè)圖看看鏈表這類數(shù)據(jù)結(jié)構(gòu)到底長(zhǎng)啥樣子嘱巾。
1.1.2 特性
每個(gè)鏈表中的節(jié)點(diǎn)都包含一個(gè)值，和指向下一個(gè)節(jié)點(diǎn)的指針诫钓。由此可以定義出節(jié)點(diǎn)的結(jié)構(gòu)：
private class Node {
public E e;
public Node next;
public Node(E e, Node next) {
this.e = e;
this.next = next;
}
public Node(E e) {
this(e, null);
}
@Override
public String toString() {
return e.toString();
}
}
如果要?jiǎng)?chuàng)建一個(gè)鏈表浓冒，如上圖1-1-1，我們只要知道一個(gè)起始的node節(jié)點(diǎn)即可尖坤。所以每個(gè)鏈表數(shù)據(jù)結(jié)構(gòu)中稳懒，包含的就是一個(gè)起始node頭節(jié)點(diǎn)。
1.2 鏈表插入元素
在一個(gè)如下的鏈表中慢味，index為2的地方场梆，插入節(jié)點(diǎn)15。步驟如下：
第一步纯路，先找到index為1的node節(jié)點(diǎn)23或油；
第二步，然后把節(jié)點(diǎn)15的next指針指向節(jié)點(diǎn)10驰唬；
第三步顶岸，把節(jié)點(diǎn)23的next指針指向15；
注意點(diǎn)：這里需要先把15節(jié)點(diǎn)的next指向10叫编，然后再把23節(jié)點(diǎn)的next指向15辖佣，順序不能打亂，要不然就找不到23節(jié)點(diǎn)后面的鏈表啦搓逾。
其實(shí)鏈表這類數(shù)據(jù)結(jié)構(gòu)卷谈，一般情況下，比較適應(yīng)于頭尾節(jié)點(diǎn)的操作霞篡，索引index的概念其實(shí)是不存在的世蔗，只是例子中為了方便表示我們插入的位置端逼，才引入了一個(gè)index的概念。
1.2.1 虛擬頭節(jié)點(diǎn)
聰明的你可能發(fā)現(xiàn)了污淋，我們?cè)谔砑釉貢r(shí)顶滩，都是先找到待添加位置的前一個(gè)位置，可是如果待添加位置的index為0呢寸爆？我們就得單獨(dú)開(kāi)設(shè)邏輯來(lái)進(jìn)行判斷礁鲁。代碼如下：
private Node head;
private int size;
public void add(E e, int index) {
if (index == 0) {
addFirst(e);
return;
}
Node preNode = head;
for (int i = 1; i < index; i++) {
preNode = preNode.next;
}
// 這三句話可以整理成一句話
// preNode.next = new Node(e, preNode.next);
Node node = new Node(e);
node.next = preNode.next;
preNode.next = node;
size++;
}
public void addFirst(E e) {
head = new Node(e, head);
size++;
}
這時(shí)，如果我們添加一個(gè)虛擬的頭節(jié)點(diǎn)而昨，就能統(tǒng)一所有的操作救氯，使得邏輯看起來(lái)更加順暢找田。
private Node dummyHead; // 虛擬頭節(jié)點(diǎn)
private int size;
public LinkedList() {
dummyHead = new Node(null, null);
size = 0;
}
public void add(int index, E e) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("index is illegal");
}
// 虛擬頭節(jié)點(diǎn)賦值給最開(kāi)始的前一個(gè)節(jié)點(diǎn)
Node preNode = dummyHead;
// 找尋index前一個(gè)節(jié)點(diǎn)的索引
for (int i = 0; i < index; i++) {
preNode = preNode.next;
}
preNode.next = new Node(e, preNode.next);
// 這三句話可以整理成一句話
// Node node = new Node(e);
// node.next = preNode.next;
// preNode.next = node;
size++;
}
1.3 鏈表的遍歷
鏈表的遍歷操作意義很大歌憨，查詢某個(gè)元素，修改某個(gè)元素等操作都會(huì)涉及到鏈表的遍歷墩衙。以下就以鏈表是否包含一個(gè)元素來(lái)展示一下查詢操作务嫡。
public boolean contains(E e) {
Node cur = dummyHead.next;
while (cur != null) {
if (cur.e.equals(e)) {
return true;
}
cur = cur.next;
}
return false;
}
1.4 鏈表刪除元素
第一步，找到待刪除元素前一個(gè)元素漆改，如下圖的23心铃；
第二步，把待刪除元素前一個(gè)元素(23)的指針指向待刪除元素（10）的后一個(gè)元素（35）挫剑。
第三步去扣，把刪除元素返回，刪除元素的下一個(gè)元素指針置空樊破，脫離鏈表愉棱。
實(shí)現(xiàn)代碼如下：
public E remove(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("index is illegal");
}
Node preNode = dummyHead;
for (int i = 0; i < index; i++) {
preNode = preNode.next;
}
Node delNode = preNode.next;
preNode.next = delNode.next;
delNode.next = null;
size--;
return delNode.e;
}
1.5 鏈表實(shí)現(xiàn)棧
鏈表在插入與刪除元素時(shí)，如果只是對(duì)頭節(jié)點(diǎn)進(jìn)行操作哲戚，那么時(shí)間復(fù)雜度都是O(1)級(jí)別的奔滑。因?yàn)椴淮嬖趯ぶ愤^(guò)程。所以用它來(lái)實(shí)現(xiàn)棧這種數(shù)據(jù)結(jié)構(gòu)最合適不過(guò)了顺少。
1.6 一些拓展
雙向鏈表朋其，每個(gè)node節(jié)點(diǎn)都有一個(gè)前指針和后指針，一般這種情況下脆炎，還會(huì)增加一個(gè)虛擬的尾節(jié)點(diǎn)用做尾指針梅猿，增加了尋址的速度。
循環(huán)雙向鏈表秒裕，可以少維護(hù)一個(gè)尾指針粒没，向頭部添加元素就是在虛擬頭節(jié)點(diǎn)前增加元素，向尾部添加元素就是在虛擬頭節(jié)點(diǎn)后插入元素簇爆。
1.7 leetcode上練習(xí)
leetcode中有許多題目癞松，以下對(duì)一些常見(jiàn)的操作進(jìn)行實(shí)現(xiàn)爽撒。看看具體實(shí)現(xiàn)的思路是什么响蓉。
1.7.1 鏈表反轉(zhuǎn)
最開(kāi)始硕勿，想出來(lái)的是以下這一種方法：在遍歷鏈表的過(guò)程中，不斷new出新的node節(jié)點(diǎn)枫甲。然后把后遍歷的元素添加到鏈表頭位置源武。代碼如下：
public ListNode reverseList(ListNode head) {
if (head == null) {
return null;
}
ListNode result = new ListNode(head.val);
ListNode curr = head;
while (curr.next != null) {
ListNode next = new ListNode(curr.next.val);
next.next = result;
result = next;
curr = curr.next;
}
return result;
}
如上代碼具體的圖文解析如下，假如傳進(jìn)來(lái)的鏈表為3想幻，5粱栖，7，8：
這種方式雖然可以完成反轉(zhuǎn)脏毯，但在反轉(zhuǎn)的過(guò)程中會(huì)不斷的new出新的節(jié)點(diǎn)闹究，有點(diǎn)浪費(fèi)空間。于是乎就在想食店，是否可以就利用原來(lái)的節(jié)點(diǎn)制造出新的鏈表渣淤，但是指針在這種情況下就得先走一步，要不然后續(xù)節(jié)點(diǎn)就會(huì)找不到吉嫩。于是就產(chǎn)生了以下代碼：
public ListNode reverseList3(ListNode head) {
if (head == null) {
return null;
}
ListNode result = new ListNode(head.val);
ListNode cur = head.next;
while (cur != null) {
// 記錄住每次循環(huán)時(shí)當(dāng)前的指針
ListNode current = cur;
// 指針先行
cur = cur.next;
current.next = result;
result = current;
}
return result;
}
最后還有一種遞歸的方式來(lái)反轉(zhuǎn)鏈表价认，關(guān)于遞歸，以后有機(jī)會(huì)單獨(dú)寫(xiě)一篇文章來(lái)進(jìn)行總結(jié)自娩。利用遞歸來(lái)解決問(wèn)題用踩，思路是把當(dāng)前問(wèn)題拆分成更小的可重復(fù)的問(wèn)題，最終忙迁，當(dāng)問(wèn)題規(guī)模小到一定程度時(shí)脐彩，可以自然求得答案（如下面當(dāng)鏈表的下一個(gè)節(jié)點(diǎn)next為空時(shí)，反轉(zhuǎn)鏈表就是本身）动漾。
private ListNode reverse(ListNode head){
// 遞歸到底的退出條件
if (head.next == null) {
return head;
}
// 不能用newHead的next指向當(dāng)前節(jié)點(diǎn)丁屎，因?yàn)閚ewHead始終沒(méi)有動(dòng)
ListNode newHead = reverse(head.next);
head.next.next = head;//鏈表循環(huán)
head.next = null;
return newHead;
}
以3，7旱眯，8為例晨川，當(dāng)循環(huán)到底后，return head;返回的就是節(jié)點(diǎn)8删豺。此時(shí)進(jìn)入上次遞歸函數(shù)體內(nèi)共虑，鏈表的示意圖如下：
經(jīng)過(guò)這句代碼
head.next.next = head;
將變成如下圖顯示，節(jié)點(diǎn)8指向了節(jié)點(diǎn)7呀页，構(gòu)成了一個(gè)循環(huán)列表了妈拌。
然后在經(jīng)過(guò)這句代碼：
head.next = null;
就變成如下這個(gè)樣子了：
到此，完成了一次遞歸操作，我們來(lái)看看這個(gè)例子中更小規(guī)模的問(wèn)題是：兩個(gè)節(jié)點(diǎn)進(jìn)行了一次指針指向的調(diào)換尘分，就是反轉(zhuǎn)猜惋。
接下來(lái)的邏輯，就是重復(fù)以上過(guò)程培愁，整個(gè)過(guò)程如下圖：
所以最終就是：節(jié)點(diǎn)還是那個(gè)節(jié)點(diǎn)著摔，只是由我愛(ài)(指向)你變成了你愛(ài)(指向)我啦啦啦～，還是雙向鏈表好定续，你有我時(shí)我也有你谍咆。咳咳～～，我們言歸正傳私股，哈哈～～摹察。
1.7.2 尋找中間節(jié)點(diǎn)
尋找鏈表中的中間節(jié)點(diǎn)，這個(gè)問(wèn)題倡鲸，最開(kāi)始肯定能夠想到的就是遍歷一下鏈表的長(zhǎng)度供嚎，然后，根據(jù)長(zhǎng)度找到中間節(jié)點(diǎn)旦签。
但是如果僅僅是這樣查坪，肯定是會(huì)被鄙視的寸宏，在leetcode上看到了一個(gè)快慢指針的方式找尋中間節(jié)點(diǎn)的方法宁炫，感覺(jué)很是巧妙。
看看我們?nèi)绾蝸?lái)理解快慢指針的：把鏈表看作一條賽道氮凝，運(yùn)動(dòng)員A速度是運(yùn)動(dòng)員B的兩倍羔巢，當(dāng)運(yùn)動(dòng)員A跑完全程，運(yùn)動(dòng)員B就剛剛好跑了一半罩阵。
我們要做的代碼如下竿秆，fast的next指針為空或者fast的next的next指針為空，則退出尋址循環(huán)稿壁。
slow = slow.next
fast = fast.next.next
完美找到中點(diǎn)幽钢，這種方式真是優(yōu)雅而又巧妙，遍歷次數(shù)減少到了n／2次傅是。
1.8 題外話
鏈表這種數(shù)據(jù)結(jié)構(gòu)是一種動(dòng)態(tài)的數(shù)據(jù)結(jié)構(gòu)匪燕，節(jié)點(diǎn)node就是一個(gè)信息存放點(diǎn)，雙向鏈表也就是一個(gè)節(jié)點(diǎn)中除了存放后指針喧笔，還會(huì)存放前指針帽驯，存放信息更多，那么就會(huì)拓展鏈表的功能书闸。但是同樣的就會(huì)增加維護(hù)的成本尼变，額外的內(nèi)存開(kāi)銷。
由此引申到生活浆劲，數(shù)據(jù)結(jié)構(gòu)和人一樣嫌术，有所長(zhǎng)必有所短哀澈。這個(gè)世界是公平的，人和事都沒(méi)有所謂的完美之說(shuō)度气，少追求完美主義日丹，多接受自身的不足點(diǎn)，看到自身閃光點(diǎn)蚯嫌，也許才是快樂(lè)生活的源泉哲虾。
