Categories
程式開發

刷了LeetCode的鍊錶專題,我發現了一個秘密!


刷了LeetCode的鍊錶專題,我發現了一個秘密!

引言

鍊錶是以節點(node)存儲的鍊式存儲結構,一個node包含一個data域(存放數據)和一個next域(存放下一個node的指針),鍊錶的各個節點不一定是連續的,它可以分為帶頭結點和不帶頭結點。頭結點僅包含next域。

刷了LeetCode的鍊錶專題,我發現了一個秘密! 1

如果不熟悉鍊錶的同學,建議先看看我的一篇文章“。在這篇文章中,主要講解使用鍊錶的小技巧,如何使用這些技巧來解題,深入解析了LeetCode中具有代表性的鍊錶題目,相信我,看了這篇文章,你再也不用擔心關於鍊錶的題目了。

1、鍊錶的幾個概念講解

事實上,鍊錶的結構比較簡單,阻礙我們理解鍊錶的常常是因為鍊錶的指針、邊界問題等,這有時會讓我們很煩躁,不要慌,我們下面一一對這下概念解析,相信你看了會有收穫。

1.1鍊錶中的的指針是什麼

我們學習C語言時,學過指針,它描述的是指向一個內存地址,在Java語言中,是不存在指針的,但是我們可以把它理解為引用。

當我們將某個變量(對象)賦值給指針(引用),實際上就是將這個變量(對象)的地址賦值給指針(引用)。

p—>next = q; //表示p节点的后继指针存储了q节点的内存地址。
p—>next = p—>next—>next; //表示p节点的后继指针存储了p节点的下下个节点的内存地址。

1.1指針指向哪兒

我們寫鍊錶代碼時,使用的指針的指來指去,很快就把我們搞糊塗了,在這種情況下很容易發生指針丟失和內存洩漏。我們先普及下這兩個概念:

指針丟失:自己定義的指針不知道指到哪裡了,沒有明確的指向。

內存洩漏:鍊錶中的節點沒有確切的指針判斷,運行時會拋出空指針異常。

我們以插入節點和刪除結點來分析指針丟失和內存洩漏的具體情況

插入節點

在節點a和節點b之間插入節點x,b是a的下一節點,p指針指向節點a,

p—>next = x;
x—>next = p—>next;

這樣的代碼會造成指針丟失和內存洩漏,因為這會導致x節點的後繼指針指向了自己本身。

正確代碼應該為:

x—>next = p—>next;
p—>next = x;

刷了LeetCode的鍊錶專題,我發現了一個秘密! 2

刪除節點

同樣的,在節點a和節點c之間刪除節點b,b是a的下一節點,p指針指向節點a,正確的代碼應該為:

p—>next = p—>next—>next;

刷了LeetCode的鍊錶專題,我發現了一個秘密! 3

在刪除節點,考慮到刪除的節點可能是鍊錶中的第一個節點,我們通常在鍊錶頭部加入哨兵(頭結點),這樣可以使得刪除鍊錶的代碼是一致的,不用再額外考慮是否是第一個節點的情況。

在鍊錶加入哨兵的代碼為:

//定义一个哨兵作为传入链表的头结点
ListNode pre =new ListNode(0);
pre.next=head;

刷了LeetCode的鍊錶專題,我發現了一個秘密! 4

1.3判斷邊界的條件

處理鍊錶問題時,要充分考慮鍊錶的邊界判斷條件,通常情況下,我們經常使用以下幾種判斷條件:

如果鍊錶為空時,代碼是否能正常工作?

如果鍊錶只包含一個結點時,代碼是否能正常工作?

如果鍊錶只包含兩個結點時,代碼是否能正常工作?

代碼邏輯在處理頭結點和尾結點的時候,是否能正常工作?

這些判斷條件需要結合自己的實際場景來使用

2、必須掌握的幾類題目

在上面的學習中,我們對鍊錶的一些易錯的概念進行了解析,下面,我們就真正的代碼實踐,我在LeetCode上刷題時發現,鍊錶題目通常分為以下幾類:

單鍊錶的反轉(LeetCode206)鍊錶中環的檢測(LeetCode141)兩個有序鍊錶的合併(LeetCode21)刪除鍊錶(LeetCode18)刪除鍊錶倒數第n個結點(LeetCode19)求鍊錶的中間結點(LeetCode876)

這幾類鍊錶題基本涵蓋了大部分知識點,在下面的學習中,我們將一一攻克它,相信掌握它們之後,在以後筆試/面試中,更能隨心所欲。

2.1單鍊錶反轉(LeetCode206)

思路:從前往後將每個節點的指針反向,即.next內的地址換成前一個節點的,但為了防止後面鍊錶的丟失,在每次換之前需要先創建個指針指向下一個節點。

class Solution {
public ListNode reverseList(ListNode head) {

if(head==null||head.next==null){
return head;
}
ListNode p1=head;
//用一个新的链表
ListNode p2=null;
while(p1!=null){
//每次更换指向之前都需要保存下一个节点
ListNode temp=p1.next;
p1.next=p2;
p2=p1;
p1=temp;
}
return p2;
}
}

2.2鍊錶中環的檢測(LeetCode141)

思路:定義兩個指針,p1和p2,指針p1每次走一步,指針p2每次走兩步,如果鍊錶中存在環,則必然會在某個時刻滿足p1==p2

public class Solution {
public boolean hasCycle(ListNode head) {
if(head==null||head.next==null){
return false;
}
ListNode slow=head;
ListNode fast=head.next;
while(fast!=null&&fast.next!=null){
if(slow==fast){
return true;
}
slow=slow.next;
fast=fast.next.next;
}
return false;
}
}

NOTE:對於快指針來說,因為一次跳兩步,如果要使用快指針作為判斷條件,fast和fast.next都需要判斷是否為空。 (不可跨級)

2.3兩個有序的鍊錶合併(LeetCode21)

思路:可以新創建一個鍊錶用於合併後的結果,合併的條件如下

兩個鍊錶都不為空

>定義一個指針,查找合適的節點並放入新創建鍊錶的下一位置

有一個鍊錶為空

>將不為空的鍊錶放入新創建鍊錶的下一位置

class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

if(l1==null){
return l2;
}
if(l2==null){
return l1;
}
ListNode result=new ListNode(0);
ListNode temp=result;
//两个链表都不为空
while(l1!=null&&l2!=null){
if(l1.val<=l2.val){ temp.next=l1; temp=temp.next; l1=l1.next; } else{ temp.next=l2; temp=temp.next; l2=l2.next; } } //有一个链表为空 if(l1==null){ temp.next=l2; } else{ temp.next=l1; } return result.next; } }

2.4刪除鍊錶(LeetCode18)

思路:可以在鍊錶頭加一個哨兵(頭結點),刪除鍊錶時先找到刪除鍊錶的上一個位置,按照刪除規則刪除即可。

class Solution {
public ListNode deleteNode(ListNode head, int val) {
if(head==null){
return null;
}
//定义一个哨兵作为传入链表的头结点
ListNode pre =new ListNode(0);
pre.next=head;

ListNode temp=pre;
while(temp!=null){
if(temp.next.val==val){
temp.next=temp.next.next;
break;
}
else{
temp=temp.next;
}
}
return pre.next;
}
}

2.5刪除鍊錶倒數第n 個結點(LeetCode19)

思路:刪除節點時要利用好哨兵(帶頭結點的鍊錶)

>* 遍歷數組的長度count

>* 找到要刪除節點的前一個位置count-n-1

>* 刪除節點

class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode pre=new ListNode(0);
pre.next=head;
ListNode temp1=pre;
ListNode temp2=pre;
int count=0;
while(temp1!=null){
temp1=temp1.next;
count++;
}

while(count-n-1>0){
temp2=temp2.next;
count--;
}
temp2.next=temp2.next.next;

return pre.next;
}
}

2.6求鍊錶的中間結點(LeetCode876)

思路:找出鍊錶中結點的個數count,然後count/2找出中間結點,刪除即可。

class Solution {
public ListNode middleNode(ListNode head) {
if(head==null) return null;
ListNode temp=head;
int count=0;
while(temp!=null){
temp=temp.next;
count++;
}
int mid=count/2;
ListNode result=head;
while(mid>0){
result=result.next;
mid--;
}
return result;
}
}

Note:實踐是檢驗真理的唯一標準,要真正的學好鍊錶這個知識點,僅僅學理論是不可靠的,我們需要多敲代碼,多思考,多寫多練,針對抽象的題目,可以舉例畫圖,來輔助的自己的思考。

3、學習鍊錶的體會

1、 函數中需要移動鍊錶時,最好新建一個指針來移動,以免更改原始指針位置。

2、 單鍊錶有帶頭節點和不帶頭結點的鍊錶之分,一般做題默認頭結點是有值的。

3、 鍊錶的內存時不連續的,一個節點佔一塊內存,每塊內存中有一塊位置(next)存放下一節點的地址。

3、 鍊錶中找環的思想:快慢指針,創建兩個指針,一個快指針:一次走兩步,一個慢指針:一次走一步,若相遇則有環,若指向null則無環。

4、 鍊錶找倒數第k個節點思想:創建兩個指針,第一個指針查詢鍊錶中結點的個數count,然後count-k確定刪除結點的位置,用第二個指針遍歷鍊錶到count -n-1個位置。

5、 反向鍊錶思想:從前往後將每個節點的指針反向,即next內的地址換成前一個節點的,但為了防止後面鍊錶的丟失,在每次換之前需要先創建個指針指向下一個節點。

總結

無論學習任何一個知識點,我們都需要在掌握術(使用方法)的基礎上,學習道(本源),學習數據結構與算法也是一樣,我們不僅要掌握如何使用它,更要掌握為什麼要是用它,相比其它的方法,它有什麼優點,難道是時間複雜度低,空間複雜度小,還是它的數據結構適合這個場景等等...

參考文獻

[1]王爭.數據結構與算法之美

[2]LeetCode中國網站

刷題組合拳推薦

筆者在過去的3個月時間裡整理常用的數據結構與算法和秒殺劍指offer,公眾號分別回複數據結構與算法,秒殺劍指offer,即可領取兩套電子書,希望能夠幫助大家。

刷了LeetCode的鍊錶專題,我發現了一個秘密! 5

刷了LeetCode的鍊錶專題,我發現了一個秘密! 6

我是Simon郎,一個想要每天博學一點點的小青年,關注我,讓我們一起進階,一起博學。

刷了LeetCode的鍊錶專題,我發現了一個秘密! 7