【宣告】：由于筆者水平有限，在今后的博文中難免會出現錯誤和不準之處，本人也非常渴望知道這些錯誤，懇請讀者批評斧正，期待您的留言評論，
文章目錄
目錄
文章目錄
嘮叨一下：做資料結構題目時不論難易，一定要畫圖理解，包括后期發布的遞回也是這樣，千萬千萬不能懶惰哦！
一、十大鏈表必刷題有哪些？
二、演算法分析及代碼示例
1.反轉鏈表（劍指offer）
2.找到鏈表的中間節點
3.找出單鏈表中倒數第k個節點（劍指offer）
4.鏈表分割：所有小于x的節點排在大于等于x的節點之前（位元組跳動筆試題）
5.洗掉已經排好序的鏈表中重復的節點（位元組跳動筆試題）
6.鏈表的回文結構（騰訊筆試題）
7.環形鏈表I：判斷鏈表是否有環（百度筆試題）
8.環形鏈表II：找入口節點（騰訊筆試題）
9.相交鏈表（劍指offer）
10.合并兩個有序的鏈表（劍指offer）
11.洗掉所有關鍵字為key的節點（劍指offer）
總結
嘮叨一下：做資料結構題目時不論難易，一定要畫圖理解，包括后期發布的遞回也是這樣，千萬千萬不能懶惰哦！
一、十大鏈表必刷題有哪些？
1、反轉鏈表 2、找到鏈表的中間節點 3、找到鏈表中倒數第k個節點 4、鏈表分割，所有小于某個數的節點都放在大于或者等于那個數的節點之前 5、洗掉已經排好序的鏈表中重復的節點 6、鏈表的回文結構 7、環形鏈表I:判斷鏈表是否有環 8、環形鏈表II:找入口節點 9、相交鏈表：找到兩個鏈表相交的起始節點 10、合并兩個已排好序的鏈表 11、洗掉所有出現關鍵字為key的節點(嘻嘻，你不會真的天真的以為只有十題吧..)
二、演算法分析及代碼示例
//無頭單向非回圈鏈表
class Node {
//實體成員沒有初始化，默認值為對應的0值，參考型別默認為null，簡單型別默認為0
public int data;//數值域---0
public Node next;//下一個節點的參考---null
public Node(int data) {
this.data = data;
this.next = null;
}
}1.反轉鏈表（劍指offer）
思路：有兩種方法：一是直接翻方向，二是利用頭插法，因為該題比較簡單，直接看代碼示例就能理解，不過在這里，筆者要再強調一遍的是，不管多簡單的題目，一定要畫圖理解，千萬不能眼高手低！！！
代碼如下（示例）：
//1、反轉鏈表
//方法一：直接翻方向（最好掌握這個方法，因為在后面的“回文結構”中也用到了這個方法）
public Node reverseList(Node head) {
Node prev = null;//需要反轉的節點的前驅
Node cur = head;//需要反轉的節點
Node newHead = null;//反轉后的單鏈表的頭
//遍歷鏈表
while(cur != null) {
Node curNext = cur.next;//需要反轉的節點的后繼
if(curNext == null) {
newHead = cur;
}
cur.next = prev;
prev = cur;
cur = curNext;
}
return newHead;
}
//方法二：頭插法（取原鏈表的節點，頭插到新鏈表）（相對于直接翻方向容易理解一些）
public Node reverseList1(Node head) {
Node cur = head;//進行頭插的節點
Node newHead = null;
while(cur != null) {
Node curNext = cur.next;//進行頭插的節點的后繼
cur.next = newHead;
newHead = cur;
cur = curNext;
}
return newHead;
}2.找到鏈表的中間節點
NB（注意）：如果有兩個中間節點，則回傳第二個
思路：利用快慢指標fast和slow，兩個都從頭開始走，fast一次走兩步，slow一次走一步，當fast == null || fast.next == null 時，slow就是中間結點
代碼如下（示例）：
public Node middleNode(Node head) {
Node slow = head;
Node fast = head;
//只要fast或者fast.next有一個為空，那么肯定走到尾了，注意別忘記加上fast.next!=null
//注意不能寫成fast.next != null && fast != null這樣，因為fast走兩步后可能為空了，再執行
//回圈fast.next可能會導致空指標例外
while(fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
3.找出單鏈表中倒數第k個節點（劍指offer）
思路：還是利用快慢指標fast和slow，fast先走k-1步，然后fast和slow每個同時走一步，當fast.next==null時，slow就是所求
public Node FindKthToTail(Node head, int k) {
//單鏈表不能為空
if(head == null) {
return null;
}
//先判斷k的合法性
//此處為了只需一次遍歷單鏈表就能解決問題，同時也為了提高時間效率，沒有加上k > size()這個
//條件，所以后面要注意空指標例外(第一個while回圈做了處理)，size()實際上是我寫的求單鏈表
//長度的方法，在此你只要將k > size()理解成"k > 單鏈表的長度"即可
if(k <= 0) {
System.out.println("k不合法！");
return null;
}
Node slow = head;
Node fast = head;
//不能讓它一直往后面走，可能會導致空指標例外
while(k - 1 > 0) {
//設定fast.next != null這個條件就是防止k大于單鏈表的長度
if(fast.next != null) {
fast = fast.next;
k--;
}else {
System.out.println("沒有這個節點！");
return null;
}
}
while(fast.next != null) {
fast = fast.next;
slow = slow.next;
}
return slow;
}4.鏈表分割：所有小于x的節點排在大于等于x的節點之前（位元組跳動筆試題）
NB：鏈表分割以后需要保證原來的資料順序不變-----所以采用“尾插法”
思路：
- 設定兩個線段的開始還有結束，分別是bs,be,as,ae
- 定義一個cur,遍歷原來的單鏈表
- 如果cur.data < x,就放到第一個線段，反之，放到第二個線段，注意，為了保證分割鏈表以后原來的資料順序不變，此處采用“尾插法”，需要注意的是，一定要判斷是不是第一次插入資料，因為第一次和其他次插入資料所執行的操作是不一樣的
- cur == null時，原來的單鏈表就遍歷完了
public Node partition(Node head, int x) {
Node bs = null;
Node be = null;
Node as = null;
Node ae = null;
Node cur = head;
while (cur != null) {
if (cur.data < x) {
//第一次插入(bs為空時)
if (bs == null) {
bs = cur;
be = cur;
} else {
be.next = cur;
be = be.next;
}
} else {
//第一次插入（as為空時）
if (as == null) {
as = cur;
ae = cur;
} else {
ae.next = cur;
ae = ae.next;
}
}
cur = cur.next;
}
//1、判斷bs是否為空，如果bs == null,回傳as
if (bs == null) {
return as;
}
//2、如果bs不為空，需要進行拼接
be.next = as;
//3、如果ae不為空，ae.next需要置為空
if (ae != null) {
ae.next = null;
}
return bs;
}5.洗掉已經排好序的鏈表中重復的節點（位元組跳動筆試題）
注意：1、已經排好序的鏈表就意味著重復的節點集中在一起，讀題時就要聯想到這一點
2、該題是將重復的節點全部洗掉干凈
思路：定義一個虛擬節點來解決問題（也就是將沒有重復出現的節點放到一個新的鏈表當中）
public Node deleteDuplication(Node head) {
Node cur = head;
Node newHead = new Node(-1);//定義的虛擬節點
Node tmp = newHead;
while(cur != null) {
//一定要加上cur.next != null這個條件，防止一直朝后走導致空指標例外(因為后面要判斷
//cur.data == cur.next.data,涉及cur.next，所以要多想一下)
if(cur.next != null && cur.data == cur.next.data) {
while(cur.next != null && cur.data == cur.next.data) {
cur = cur.next;
}
cur = cur.next;//多走一步(因為要把重復的節點全部洗掉掉)
}else {
tmp.next = cur;
tmp = tmp.next;
cur = cur.next;
}
}
tmp.next = null;//最后一定不要忘記了將尾結點的next置為空
return newHead.next;
}6.鏈表的回文結構（騰訊筆試題）
注意：用到了前面的反轉鏈表和找鏈表的中間節點這兩個方法的演算法思想
思路：1、找到中間節點
2、翻轉鏈表后半部分的節點
3、先從奇數個節點入手，最后再考慮偶數個節點的情況
public boolean chkPalindrome(Node head) {
//單鏈表為空，肯定不是回文結構
if(this == null) {
return false;
}
//只有頭結點自己，肯定是回文結構
if(head.next == null) {
return true;
}
//1、找到單鏈表的中間節點
Node fast = head;
Node slow = head;
while(fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
//2、開始反轉單鏈表的后半部分 slow肯定在中間位置
Node cur = slow.next;
while(cur != null) {
Node curNext = cur.next;
cur.next = slow;
slow = cur;
cur = curNext;
}
//slow是最后的節點了
//3、開始一個從頭走，一個從尾走
while(slow != head) {
if(slow.data != head.data) {
return false;
}
//判斷偶數的情況(一定要注意的是不能比較的是元素大小！！！)
if(head.next == slow) {
return true;
}
slow = slow.next;
head = head.next;
}
return true;
}7.環形鏈表I：判斷鏈表是否有環（百度筆試題）
思路：本題很簡單，利用快慢指標做即可
public boolean hasCycle(Node head) {
Node fast = head;
Node slow = head;
//如果有環，必然不會存在null
while(fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if(fast == slow) {
return true;
}
}
return false;
}8.環形鏈表II：找入口節點（騰訊筆試題）
思路：1、設環的長度為C，相遇時fast走了N圈，從頭到入口點的距離為X，入口點到相遇點為Y；
2、如果有環，fast和slow相遇的時候，fast走的路程是slow的兩倍，2 * (X + Y) = X + NC + Y----->X + Y = NC----->X = NC - Y
3、NC是一個定值，當N == 1時，相遇點到入口點的距離就是X，此時使用兩個參考，一個 從頭開始走，一個從相遇點開始走，當二者相遇的時候就是入口點
public Node detectCycle(Node head) {
Node fast = head;
Node slow = head;
//如果有環，必然不會存在null
while(fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if(fast == slow) {
break;
}
}
if(fast == null || fast.next == null) {
return null;
}
//相遇后，即有環，此時使用兩個參考，一個從頭開始走，一個從相遇點（此時的slow和fast就在相
//遇點）開始走，當二者相遇的時候就是入口點
slow = head;
while(slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
9.相交鏈表（劍指offer）
思路：1、求兩條單鏈表的長度
2、計算兩條單鏈表的差值
3、讓長的鏈表先走差值步，后面詳細步驟見代碼塊即可求出兩鏈表第一次相交節點
public Node getIntersectionNode(Node headA, Node headB) {
//1、求長度，走差值步
int lenA = 0;
int lenB = 0;
Node pl = headA;
Node ps = headB;
while(pl != null) {
lenA++;
pl = pl.next;
}
while(ps != null) {
lenB++;
ps = ps.next;
}
//注意此時pl，ps位置不再是頭了，需要人為設定
pl = headA;
ps = headB;
//len要放到這個位置計算，最基本的都忘記了！！！
int len = lenA - lenB;
//保證pl里面放的是長鏈表，ps里面放的是短鏈表
if(len < 0) {
pl = headB;
ps = headA;
len = lenB - lenA;
}
//長的鏈表走差步值
for(int i = 0; i < len; i++) {
pl = pl.next;
}
//2、ps和pl一定在同一個起跑線上
//設定ps != pl這個條件就是為了相交的時候停下來
//別忘了pl != null && ps !=null 這個條件,其實也可以省去，因為兩鏈表剩下的節點一樣長！
while(ps != pl && pl != null && ps != null) {
ps = ps.next;
pl = pl.next;
}
//二者相等也可能是兩條鏈表都為空了
if(pl == ps && pl != null) {
return pl;
}
return null;
}10.合并兩個有序的鏈表（劍指offer）
思路：利用虛擬節點即可
public Node mergeTwoLists(Node headA, Node headB) {
//開辟一個虛擬節點
Node newHead = new Node(-1);
Node tmp = newHead;
while(headA != null && headB != null) {
if(headA.data < headB.data) {
tmp.next = headA;
headA = headA.next;
tmp = tmp.next;
}else {
tmp.next = headB;
headB = headB.next;
tmp = tmp.next;
}
}
if(headA != null) {
tmp.next = headA;
}
if(headB != null) {
tmp.next = headB;
}
return newHead.next;
}11.洗掉所有關鍵字為key的節點（劍指offer）
思路：本題比較簡單，但是最后別忘記了要回過頭來判斷第一個節點
public void removeAllKey(Node head, int key) {
//單鏈表為空時
if(head == null) {
return;
}
//需要注意的是始終要保證prev是cur的前驅
Node prev = head;
Node cur = head.next;//代表要洗掉的節點
while(cur != null) {
if(cur.data == key) {
prev.next = cur.next;
cur = cur.next;
}else {
prev = cur;
cur = cur.next;
}
}
//最后再判斷首節點
if(head.data == key) {
head = head.next;
}
}
總結
與其說它是十大鏈表必刷題，不如把“十大”改成“十類”，因為LeetCode和牛客網等刷題網站上面至少80%的題目都是這十類題目本身，或是其變形形式，中心演算法思想是一致的，稍稍改動即可，不過若要會做變形形式，首先需要將這些最基本的原題爛熟于心，資料結構的重要性不用說大家都明白，鏈表在資料結構中也是舉足輕重的，
可能我們在聽老師講課的時候，或者就拿上面的代碼舉例吧，我們聽或者看的時候，能聽懂也能看懂，但是到自己實作起來就不是那么一回事了，筆者本人也是這樣，究其原因呢，還是題目刷少了，代碼量跟不上！所以平時要多練習，筆者自己呢，也是剛剛開始刷LeetCode沒多長時間，希望與大家共同進步，
此處需要敲黑板——若要真正掌握上面的題目，我們最起碼要練習五遍以上，而且每一遍都要畫圖理解，包括之后即將發布的遞回也是這樣，我們處在一個非常美好的時代，時不我待，萬萬不能懶惰呀鐵子們，我自己也是！
還有還有，感謝鐵子們能看到最后，蟹蟹啦！
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/316607.html
標籤：java