文章簡述
在本次的文章中，按照個人的刷題計劃，會分享關于鏈表的 3 道簡單級別的算法題（可是依然感覺不簡單）
但是不要緊，從本篇文章開始分享的算法題個人都會把關于這道題的全部代碼寫出來，并用debug的形式，分解每一步來整理出來。
通過還原題目場景，用 debug 調(diào)試的方式去分析，印象更加深刻些。
本篇文章中共有 3 道題目。
一，合并兩個有序鏈表
1.1 題目分析
看到這道題的時候，第一反應就是先將兩個鏈表合并，然后再排序。嗯。。。不用想，絕對的暴力寫法。
或者是循環(huán)兩個鏈表，然后兩兩相比較，就像：
for(){
for(){
if(){}
}
}
好吧，其實這道題精華在于可以使用遞歸，這個。。。來個草圖簡單描述下。
第一步：
兩個鏈表的首節(jié)點進行比較
兩個節(jié)點相等，則使 L2 鏈表【1】，和 L1 鏈表的【2】進行比較
注意：
L1節(jié)點【1】和L2節(jié)點【1】比較完成后，需要修改1.next指針，以指向它的下個節(jié)點。
第二步：
現(xiàn)在我們獲取到了 L2 鏈表【1】，那它的 next 指向誰？也就是 L2 鏈表【1】去和 L1 鏈表的【2】進行比較。
比較完成后，L2 鏈表【1】的 next 就指向了 L1 鏈表【2】，接著以此類推。
L2 鏈表【3】去和 L1 鏈表【4】比較。
最后 L1 鏈表【4】和 L2 鏈表【4】比較。
全部比較完成后，整個鏈表就已經(jīng)排序完成了。
遞歸的方式就在于，兩兩節(jié)點進行比較，當有一個鏈表為null時，表示其中一個鏈表已經(jīng)遍歷完成，那就需要終止遞歸，并將比較結果進行返回。
可能只是單純的畫圖并不好理解，下面用代碼 debug 的方式去分析，還請耐心往下看。
1.2 代碼分析
按照題意需要先創(chuàng)建 2 個單鏈表，具體的創(chuàng)建方式可以參考本人的第一篇文章《手寫單鏈表基礎之增，刪，查！附贈一道鏈表題》。不多說，先初始化節(jié)點對象。
class ListNode {
/**
* 數(shù)據(jù)域
*/
int val;
/**
* 下一個節(jié)點指針
*/
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 +
'}';
}
}
定義新增鏈表方法。
public ListNode add(ListNode node) {
// 1，定義輔助指針
ListNode temp = nodeHead;
// 2，首先判斷當前節(jié)點是否為最后節(jié)點
if (null == temp.next) {
// 當前節(jié)點為最后節(jié)點
temp.next = node;
return nodeHead;
}
// 3，循環(huán)遍歷節(jié)點，如果當前節(jié)點的下個節(jié)點不為空，表示還有后續(xù)節(jié)點
while (null != temp.next) {
// 否則將指針后移
temp = temp.next;
}
// 4，遍歷結束，將最后節(jié)點的指針指向新添加的節(jié)點
temp.next = node;
return nodeHead.next;
}
接著創(chuàng)建 2 個鏈表。
/**
* 定義L1鏈表
*/
ListNode l11 = new ListNode(1);
ListNode l12 = new ListNode(2);
ListNode l13 = new ListNode(4);
MergeLinkedList l1 = new MergeLinkedList();
l1.add(l11);
l1.add(l12);
/**
* 返回新增完的L1鏈表
*/
ListNode add1 = l1.add(l13);
/**
* 定義L2鏈表
*/
ListNode l21 = new ListNode(1);
ListNode l22 = new ListNode(3);
ListNode l23 = new ListNode(4);
MergeLinkedList l2 = new MergeLinkedList();
l2.add(l21);
l2.add(l22);
/**
* 返回L2鏈表
*/
ListNode add2 = l2.add(l23);
我們先把上述圖中使用遞歸的代碼貼出來。
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
/**
* 如果L1鏈表為null，終止遞歸
*/
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}
/**
* 按照圖中的描述，兩兩比較鏈表的節(jié)點
*/
if (l1.val <= l2.val) {
/**
* L1的節(jié)點比L2的小，按照圖中就是需要比較L1鏈表的下個節(jié)點
* l1.next 就是指當比較出節(jié)點大小后，需要修改指針的指引，將整個鏈表全部串聯(lián)起來
*/
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
/**
* 同理，與上個if判斷一樣
*/
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
}
1.3 debug 調(diào)試
1.3.1 L1 鏈表已經(jīng)創(chuàng)建完成，同理 L2 也被創(chuàng)建完成。
1.3.2 比較兩個鏈表的首節(jié)點
注意：
l1.next是指向遞歸方法的，也就是上圖中我們描述的l1鏈表【1】指向了l2鏈表【1】，但是L2鏈表【1】又指向誰？開始進入遞歸
1.3.3 如上圖，開始比較 L2 鏈表【1】與 L1 鏈表的【2】
1.3.4 比較 L1 鏈表【2】與 L2 鏈表【3】
1.3.5 后面操作是一樣的，下面就直接展示最后兩個節(jié)點比較
這里已經(jīng)到最后兩個節(jié)點的比較。
這個時候 L1 鏈表先遍歷完成，需要終止遞歸，返回 L2 鏈表。為什么返回 L2 鏈表？直接看圖。
因為最后一步比較的是 L1 鏈表【4】和 L2 鏈表【4】，也就是說 L2 鏈表【4】是最后的節(jié)點，如果返回 L1 鏈表，那 L2 鏈表【4】就會被丟棄，可參考上面圖解的最后一張。
重點來了！！！
重點來了！！！
重點來了！！！
L1 鏈表已經(jīng)遍歷完成，開始觸發(fā)遞歸將比較的結果逐次返回。
這是不是我們最后 L1 鏈表【4】和 L2 鏈表【4】比較的那一步，是不是很明顯，l1.next 指向了 l1 的節(jié)點【4】，而 L1 節(jié)點也就是它最后的節(jié)點【4】，和我們那上面圖解中最后的結論一樣。
再接著執(zhí)行下一步返回。
L2 鏈表的【3】指向了 L1 鏈表的【4】
同理，按照之前遞歸的結果以此返回就可以了，那我們來看下最終的排序結果。
二，刪除排序鏈表中的重復元素
2.1 題目分析
初次看這道題好像挺簡單的，這不就是個人之前寫的第一篇文章里面，刪除鏈表節(jié)點嗎！
仔細審題其實這道題要更簡單些，因為題中已說明是一個排序鏈表，因此我們只需要將當前節(jié)點與下一個節(jié)點進行比較，如果相等則直接修改 next 指針即可。
2.1 代碼分析
同樣是鏈表的定義，與上面第一題中的創(chuàng)建是一樣的，只不過我們是需要再重新創(chuàng)建一個單鏈表。
ListNode l1 = new ListNode(1);
ListNode l2 = new ListNode(1);
ListNode l3 = new ListNode(3);
ListNode l4 = new ListNode(4);
ListNode l5 = new ListNode(4);
ListNode l6 = new ListNode(5);
NodeFun nodeFun = new NodeFun();
nodeFun.add(l1);
nodeFun.add(l2);
nodeFun.add(l3);
nodeFun.add(l4);
nodeFun.add(l5);
ListNode listNode = nodeFun.add(l6);
創(chuàng)建完成后，接著看去重復的代碼。
public ListNode deleteDuplicates(ListNode head) {
/**
* 定義輔助指針
*/
ListNode temp = head;
/**
* 判斷當前節(jié)點和下一個節(jié)點不能為空，因為是需要將當前節(jié)點和下一個節(jié)點進行比較的
*/
while (temp != null && temp.next != null) {
/**
* 如果節(jié)點值相同
*/
if (temp.val == temp.next.val) {
/**
* 表示當前節(jié)點與下一個節(jié)點的值相同，則移動指針
*/
temp.next = temp.next.next;
} else {
/**
* 必須移動指針，否則會產(chǎn)生死循環(huán)
*/
temp = temp.next;
}
}
return head;
}
}
2.2 debug 調(diào)試
2.2.1 按照初始化的鏈表，應該是首節(jié)點【1】和第二個節(jié)點【1】進行比較。
不用說兩個節(jié)點是相等的，那下一步進入 if 判斷，就是修改指針的指向。
此時第二個節(jié)點【1】已經(jīng)沒有被 next 指引了，就會被 GC 回收掉。
2.2.2 下一步就是節(jié)點【1】和節(jié)點【3】進行比較
兩個節(jié)點不相等，進入 else 將輔助指針移動到下個節(jié)點。
那么剩下的節(jié)點判斷也都是一樣的，我們最后看下打印的結果。
三，環(huán)形鏈表
3.1 題目分析
如果這個鏈表里面有環(huán)，其中一個節(jié)點必然是被指針指引了一次或者多次（如果有多個環(huán)的話）。因此個人當時簡單的做法就是遍歷鏈表，把遍歷過的節(jié)點對象保存到 HashSet 中，每遍歷下一個節(jié)點時去 HashSet 中比對，存在就表示有環(huán)。
而這道題沒有設置過多的要求，只要有環(huán)返回 boolean 就好。
還有一種巧妙的寫法，使用快慢指針的思想。
這種方式大致意思就是說，快慢指針比作龜兔賽跑，兔子跑的快，如果存在環(huán)那么兔子就會比烏龜先跑進環(huán)中。那么它們就會在某個節(jié)點上相遇，相遇了也就說明鏈表是有環(huán)的。
那么，你們問題是不是來了？這不公平啊，【兔子】本來就比【烏龜】跑的快，那咋兔子還先跑了。
試想，如果它倆都在一個節(jié)點上跑，那它們從開始不就是相遇了，因為我們我們是設定如果在一個節(jié)點上相遇，表示鏈表是有環(huán)的。所以，這不是“不打自招“了！
比賽開始，這【兔子大哥】有點猛啊，一下跑兩個節(jié)點。
果然，有情人終成眷屬，它們相遇了。
3.2 代碼分析
這次創(chuàng)建鏈表的時候，就不能單純是個單鏈表了，還得加個環(huán)。
ListNode l1 = new ListNode(3);
ListNode l2 = new ListNode(2);
ListNode l3 = new ListNode(0);
ListNode l4 = new ListNode(-4);
/**
* 給主角加個環(huán)
*/
l4.next = l2;
NodeFun nodeFun = new NodeFun();
nodeFun.add(l1);
nodeFun.add(l2);
nodeFun.add(l3);
ListNode listNode = nodeFun.add(l4);
那就一起來找環(huán)吧。
public boolean hasCycle(ListNode head) {
ListNode temp = head;
if(null == head){
// 為空表示沒有環(huán)
return false;
}
// 1，set集合保存遍歷過的節(jié)點，如果新的節(jié)點已經(jīng)在set中，表示存在環(huán)
// 2，使用快慢指針的思想
// 定義慢指針
ListNode slow = head;
// 定義快指針
ListNode fast = head.next;
// 循環(huán)，只要2個指針不重合，就一直循環(huán)
while(slow != fast){
// 如果2個指針都到達尾節(jié)點，表示沒有環(huán)
if(fast == null || fast.next == null){
return false;
}
// 否則就移動指針
slow = slow.next;
fast = fast.next.next;
}
return true;
}
3.3 debug 調(diào)試
所以，尷尬的事情來了，這玩意 debug 不了啊。如果存在環(huán)，那么 while 循環(huán)是不會進來的。
那就直接看下結果吧。
如果把環(huán)去掉就是？
那還用猜？沒有光環(huán)了肯定。。。
作者：奮進的小樣
原文鏈接：https://www.cnblogs.com/fenjyang/p/14426665.html
