鏈表算法題二，還原題目，用debug調試搞懂每一道題
- 2021 年 2 月 26 日
- 筆記
文章簡述
大家好，本篇是個人的第4篇文章。
承接第3篇文章《開啟算法之路，還原題目，用debug調試搞懂每一道題》，本篇文章繼續分享關於鏈表的算法題目。
本篇文章共有5道題目
一，反轉鏈表（經典題目）
1.1.1 題目分析
反轉鏈表是經典的題目，題中信息描述很清晰，給定一個單鏈表，將其反轉。
先說說有什麼思路呢？從題中給的案例輸出結果看，是不是只需要將輸入的鏈表的指針改成相反方向，就可以得到要輸出的結果。
就好比如下圖所示：
但是問題來了，我們是單鏈表，是沒辦法將下個節點直接指向該節點的上個節點。
因此就需要定義一個輔助指針，用來指向該節點的上個節點，這樣就能完成，如下圖所示。
那按照我們上面分析也就是將cur指針指向pre節點就可以了。
注意：此處有坑
當我們將當前節點【cur】指向上一個節點【pre】的時候，如何將指針向下移動呢？
此時的節點【cur】已經指向了上一個節點【pre】了，所以我們還需要一個臨時變量去保存當前節點的下個節點，具體為什麼這麼做，我們在下面代碼演示的時候debug看下過程。
接着我們上面的步驟，將指針向下移動，如圖所示。
移動指針後，再將當前節點的next指針指向上一個節點。
最後當前節點沒有下個節點的時候，就結束遍歷，如圖所示。
1.1.2 代碼分析
按照套路，先初始化節點對象。
class ListNode {
int val;
ListNode next;
ListNode() {
}
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
@Override
public String toString() {
return "ListNode{" +
"val=" + val +
'}';
}
}
創建單鏈表結構。
// 創建單鏈表
ListNode l1 = new ListNode(1);
ListNode l2 = new ListNode(2);
ListNode l3 = new ListNode(3);
ListNode l4 = new ListNode(4);
ListNode l5 = new ListNode(5);
NodeFun nodeFun = new NodeFun();
nodeFun.add(l1);
nodeFun.add(l2);
nodeFun.add(l3);
nodeFun.add(l4);
// 返回創建的鏈表
ListNode node = nodeFun.add(l5);
反轉鏈表的代碼。
public ListNode reverseListIteration(ListNode head) {
// 定義上節點輔助指針
ListNode pre = null;
// 定義當前節點輔助指針
ListNode cur = head;
// 循環當前節點不為空
while (null != cur) {
// 臨時變量保存當前節點的下個節點
ListNode temp = cur.next;
// 當前節點的next指向上節點
cur.next = pre;
// 上節點向下移動
pre = cur;
// 當前節點指向下個節點
cur = cur.next;
}
return pre;
}
1.1.3 debug調試
節點初始化完成了，按照分析我們定義了2個節點，如上圖第一次遍歷【pre】節點是null，【cur】從第一個節點開始。
下一步debug調試我們先不急，回顧之前說的一個問題，為什麼要將當前節點的下一個節點用臨時變量保存，那我們直接看debug調試。
第一次遍歷的時候，修改完指針後當前節點已經指向上一個節點了，再看上述題目分析的圖解。
這就是為啥要先把當前節點的下個節點緩存起來。
上圖debug我們看出，【cur】當前節點的指針已經指向null，下一步就是移動指針指向下一個節點。
我們再接着進行debug調試，按照上述分析，第二步循環就是將節點【2】指向上一個節點【1】，如下圖所示。
現在當前節點【cur】已經指向【2】，那它的下個節點就是【1】，如下圖所示。
經過上面的兩步循環，成功的將指針進行了反轉，剩下的節點循環也就如出一轍了。
當循環到最後節點【5】時，下個節點為null，此時結束while循環，而節點【5】也是指向了上一個節點【4】。
最後我們再看下運行結果。
二，迴文鏈表
1.2.1 題目分析
如果做過字符串的算法題，裏面有個迴文字符串的題目。沒錯，它倆的意思是一樣的。
看題目描述得知一個鏈表是不是迴文鏈表，就是看鏈表就是看鏈表正讀和反讀是不是一樣的。
假如說，我們拿到了後半部分鏈表，再將其反轉。去和鏈表的前半部分比較，值相等就是迴文鏈表了。
注意：
這種方式會破壞原鏈表的結構，為保證題目的一致性，最後再將鏈表再重新拼接
另外一種解題方式為：將整個鏈表節點遍歷保存到數組中，而數組是有下標，並可以直接獲取數組的大小，那麼只需從數組的首尾去判斷即可
反轉鏈表上一道題我們已經分享了，現在重點是如何獲取後半部分的鏈表。
我們再說說快慢指針的思想，通常我們定義2個指針，一個移動快，一個移動慢。詳細的案例可以參考本人上一篇文章《開啟算法之路，還原題目，用debug調試搞懂每一道題》，有一道關於快慢指針的題目。
定義慢指針每次移動1個節點，快指針每次移動2個節點，當然我們是需要保證快節點的下下個個節點不為空。
slow = slow.next;
fast = fast.next.next;
其實快慢指針的思想就是，假設鏈表是一個迴文鏈表，快指針比慢指針是多走一步，當快指針走完的時候，慢指針也就剛好走到該鏈表的一半。
上圖中slow指針正好走到鏈表的一半，此時也就得到鏈表的後半部分了，即slow.next。
1.2.2 代碼分析
老套路，先創建一個迴文鏈表。
ListNode l1 = new ListNode(1);
ListNode l2 = new ListNode(2);
ListNode l3 = new ListNode(2);
ListNode l4 = new ListNode(1);
NodeFun nodeFun = new NodeFun();
nodeFun.add(l1);
nodeFun.add(l2);
nodeFun.add(l3);
ListNode head = nodeFun.add(l4);
獲取後半部分鏈表代碼。
private ListNode endOfFirstHalf(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
反轉鏈表的代碼與上題目是一樣的。
最後將兩個鏈表進行判斷是否是一樣的。
// 判斷是否迴文
ListNode p1 = head;
ListNode p2 = secondHalfStart;
boolean flag = true;
while (flag && p2 != null) {
if (p1.val != p2.val) {
flag = false;
}
p1 = p1.next;
p2 = p2.next;
}
1.2.3 debug調試
先獲取鏈表的後半部分。
debug開始循環後，fast直接走到鏈表的第3個節點【2】
slow.next就是鏈表的後半部分，再將後半部分進行鏈表反轉
最後我們也就得到如下2個鏈表。
最後將這2個鏈表進行比較是否相等，相等則是迴文鏈表。
三，鏈表的中間節點
1.3.1 題目分析
獲取鏈表的中間節點乍一看和迴文鏈表中使用快慢指針獲取後半鏈表有點類似呢？
沒錯，這波操作是類似的，但也並不是完全一樣，其主要思想還是快慢指針。
換句話說，如果你已理解了上面的題，那這道題也就不是什麼事了。話不多說，先來分析一波。
同樣我們還是定義slow慢指針每次移動一個節點，fast快指針每次移動2個節點。
那麼fast快指針移動到最後節點時，slow慢指針也就是要返回的鏈表。
我想，你是不是有個疑問。就是為什麼慢指針是移動一個節點，快節點移動2個節點？如果是偶數個節點，這個規則還正確嗎！那就驗證下。
為了方便，就繼續上面節點的遍歷。
題目中描述，如果有2個中間節點，返回第二個節點，所以返回節點【4，5，6】也就符合要求了
1.3.2 代碼分析
創建鏈表結構。
ListNode l1 = new ListNode(1);
ListNode l2 = new ListNode(2);
ListNode l3 = new ListNode(3);
ListNode l4 = new ListNode(4);
ListNode l5 = new ListNode(5);
NodeFun nodeFun = new NodeFun();
nodeFun.add(l1);
nodeFun.add(l2);
nodeFun.add(l3);
nodeFun.add(l4);
ListNode head = nodeFun.add(l5);
獲取後半部分鏈表代碼。
// 快慢指針
ListNode slow = head;
ListNode fast = head;
while(fast != null && fast.next != null){
//移動指針
fast = fast.next.next;
slow = slow.next;
}
return slow;
1.3.3 debug調試
快指針移動到節點【3】，慢指針移動到節點【2】
接着再走一步，快指針移動到節點【5】，慢節點移動到節點【3】，到此也就滿足題意的要求了。
四，鏈表中倒數第k個節點
1.4.1 題目分析
這道題要求就是返回倒數K個節點，最笨的辦法就是參考上面鏈表反轉，先將鏈表反轉。獲取前K個節點，將獲取的節點再次進行反轉即可得到題目要求。
但是顯然這種方式只能滿足答案輸出，經過上面的3道題目，有沒有得到什麼啟發呢？
是的，這道題依然可以使用雙指針解決，是不是感覺雙指針可以解決所有的鏈表問題了（QAQ）。
再仔細一想，是不是感覺和上一道《鏈表的中間節點》題目很類似？獲取鏈表的中間節點是返回後半部分節點，而本道題是要求返回指定K個節點。
那就直接說結論吧，同樣是定義快慢指針。只不過在上道題中快指針是每次移動2個節點，本道題中給定的K，就是快指針移動的節點個數。
同樣初始化指針都在首節點，如果我們先將fast指針移動K個節點。
到此才算初始化節點完成，剩下的操作就是遍歷剩下的鏈表，直到fast指針指向最後一個節點。
一直遍歷到fast節點為null，此時返回slow指針所指引的節點。
1.4.2 代碼分析
初始化鏈表，由於和前幾道題的操作是一樣的，此處就不在展示。
獲取倒數第K個節點的代碼。
public ListNode getKthFromEnd(ListNode head, int k) {
ListNode slow = head;
ListNode fast = head;
// 先將快指針向前移動K
while (k-- > 0) {
fast = fast.next;
}
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
1.4.3 debug調試
按照上面圖解分析，fast快指針指向節點【3】的時候才算真正初始化快慢指針完成。
當快指針指向節點【5】時，slow慢節點指向節點【3】
注意：中間省略了一步，即慢指針指向節點【2】時，快指針指向節點【4】
節點【5】是最後一個節點，再次進入while循環。
最後一次循環時，慢指針指向了4，快指針下一個節點已經為null，此時結束循環。
五，移除重複節點
1.5.1 題目分析
這道題和上一篇中的題目【刪除排序鏈表中的重複元素】是一樣的，簡單的做法即利用Set集合保存未重複的節點，再遍歷鏈表判斷是否已存在Set集合中。
因此本道題就不在多分析，直接貼上代碼。
1.5.2 代碼分析
Set<Integer> set = new HashSet<>();
ListNode temp = head;
while(temp != null && temp.next != null){
set.add(temp.val);
if(set.contains(temp.next.val)){
temp.next = temp.next.next;
}else{
temp = temp.next;
}
}
return head;
}
六，總結
本次文章共分享總結5道題目，仔細分析有沒有發現這些題套路都是一樣的。都利用了雙指針的思想，通過一定的規則移動快慢指針獲取指定鏈表節點。
本次的5道題目和上次的3道題目，基本已經包含了鏈表簡單題目的所有類型。當你把本篇文章的題目看完後，關於鏈表的簡單題目你也已經做完了。
本人已經將鏈表的所有簡單題目刷完，總結出來的結論即套路都是一樣的。簡單來說，大部分的題目都可以利用雙指針，遞歸，數組來完成。
在下篇文章中會對鏈表的簡單題目做一個小總結。
最後，求關注
原創不易，每一篇都是用心在寫。如果對您有幫助，就請一鍵三連（關注，點贊，再轉發）
我是楊小鑫，堅持寫作，分享更多有意義的文章。
感謝您的閱讀，期待與您相識！
