鏈表演算法題之中等級別，debug調試更簡單

2021 年 3 月 4 日
筆記

文章簡述

大家好，本篇是個人的第 5 篇文章

從本篇文章開始，分享關於鏈表的題目為中等難度，本次共有 3 道題目。

一，兩數相加

1.1 題目分析

題中寫到數字是按照逆序的方式存儲，從進位的角度看，兩兩節點相加我們是可以直接將進位傳遞到下一組兩兩節點相加。

比如題中第二組節點【4】和節點【6】相加結果為 10，而 10 就需要進位，也就是說該節點只能保存數字【0】，而進位【1】就要傳遞到下一組節點相加。

那再整理下思路。

如果兩個鏈表的節點數是相等的，那隻需要依次將兩兩節點進行相加。如果節點數是不相等的，比如。

L2 鏈表少了一個節點，像這種情況我們就需要在高位用【0】進行補位。

我們再回到題中的案例，而上面說的位數不夠也是需要考慮的一種情況。再一步步分析下如何進行兩兩節點相加。

第一組節點相加為2+5=7，不滿足進位。創建一個新的鏈表保存相加後的數，那此時鏈表第一個節點數為【7】。

接著是4+6=10，此時滿足進位要求，按照題目要求和我們上面的分析，需要將低位【0】保存到節點，高位【1】傳遞到下一組節點。

那現在進行最後一組相加3+4=7，但是還有重要一步不能丟，即上一組節點相加時，還有高位進 1，那最後的結果是 3+4+1=8。

最後將上面相加的結果用鏈表進行保存，那麼結果為。

同理，如果位數不足時用【0】進行補位也是一樣的方式。

1.2 程式碼分析

老方式，先創建單鏈表

				// 創建鏈表-L1
        ListNode l1 = new ListNode(2);
        ListNode l2 = new ListNode(4);
        ListNode l3 = new ListNode(3);

        ListNodeFun listNodeFun = new ListNodeFun();
        listNodeFun.add(l1);
        listNodeFun.add(l2);
        ListNode listNode1 = listNodeFun.add(l3);

        ListNodeFun listNodeFun2 = new ListNodeFun();
        // 創建鏈表-L2
        ListNode l11 = new ListNode(5);
        ListNode l22 = new ListNode(6);
        ListNode l33 = new ListNode(4);
        listNodeFun2.add(l11);
        listNodeFun2.add(l22);
        ListNode listNode2 = listNodeFun2.add(l33);

兩數相加程式碼

    if(null == l1 || null == l2){
            return null;
        }
        // 初始化頭指針
        ListNode head = new ListNode();
        ListNode cur = head;
        // 定義變數保存進位值
        int temp = 0;
        while(null != l1 || null != l2){
            // 獲取每個節點的值
            int x = l1 == null ? 0 : l1.val;
            int y = l2 == null ? 0 : l2.val;
            // 兩數相加
            int sum = x + y + temp;
            // 獲取相加結果
            temp = sum  / 10;
            // 獲取低位（個位）
            sum = sum % 10;
            // 創建新的節點
            cur.next = new ListNode(sum);
            // 移動指針
            cur = cur.next;
            // 移動鏈表指針，要判斷為空，否則會空針
            if(null != l1){
                l1 = l1.next;
            }
            if(null != l2){
                 l2 = l2.next;
            }
        }
        if(1 == temp){
            cur.next = new ListNode(1);
        }
        return head.next;
    }

1.3 debug 調試

第一步，2+5

兩個鏈表的首節點相加，結果為 7。

【7】不需要進位，創建新的鏈表進行保存。

第二步，4+6

結果為 10 就需要進位，將個位上的【0】保存到節點中，十位上【1】需要進行進位。

第三步，3+4+1

最後看下運行結果

簡單總結下，這道題並不算難，但需要考慮清楚當節點相加時是否需要進行補位的情況。

二，刪除鏈表的倒數第 N 個結點

2.1 題目分析

這道題，是不是似曾相識？

沒錯，在上一篇文章中《鏈表演算法題二，還原題目，用 debug 調試搞懂每一道題》有一道題是【鏈表中倒數第 k 個節點】。但是這兩道題之間略有不同，上一篇文章中的題目是返回倒數第 K 個節點，本道題中是移除第 K 個節點，返回其他完整鏈表。

那麼這兩道題相似度很高，是不是套路也是一樣。

上一道題我們使用了雙指針的方式，那本道題也是一樣的。所以上一道題如果搞懂了，那這道所謂中等級別的題也就成簡單級別的了。雖然本人目前題量不多，但是如果善於總結的話，套路確實很接近，反正這個題我是直接寫出來了，哈哈（開玩笑）。

話又說回來，分析題中的含義，假設移除節點【4】，按照雙指針的方式，那就是一個慢指針指向節點【3】，快指針指向節點【5】。將節點【3】的下下個 next 指向節點【5】，即可移除節點【4】。

參考上一道題的方式，需要將【fast】快指針先移動 K 個節點，初始化指針位置。

注意：移除節點後，是需要反回其它完整的鏈表節點。但是有一種情況有坑，先看下圖

鏈表只有一個節點並移除，正確結果應該是返回空。像這種情況是不能直接返回 head 鏈表，因此是需要創建頭指針來指引原始的鏈表，如下圖。

所以定義雙指針的起始節點位置就是 head 節點。

按照套路先將快指針移動 K 個節點

剩下的操作即移動快慢指針，直到 fast 指針移動到最後一個節點。
（1）

（2）

（3）

最後更改 slow 指針直接指向 fast 指針指向的節點即可。

2.2 程式碼分析

創建鏈表的程式碼同上題一樣，本道題只需要創建一個 1-5 節點的鏈表。

直接貼上刪除節點的程式碼

public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode pre = new ListNode();
        pre.next = head;
        // 定義雙指針
        ListNode slow = pre;
        ListNode fast = head;
        // 先將快指針移動n個節點
        while(--n>0){
            fast = fast.next;
        }
        while(fast.next != null){
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return pre.next;
    }

2.3 debug 調試

我們先 debug 調試看下初始化節點位置後，快慢指針的位置。

接著進入第 2 個 while 循環，將剩餘的節點遍歷完。

這一步 slow 指針到節點【1】，fast 指針到節點【3】

下一步 slow 指針到節點【2】，fast 指針到節點【4】，直接看最後一步 slow 指針到節點【3】，fast 指針到節點【5】

節點【5】即最後一個節點，此時退出循環，最後將 slow 指針 next 指向 fast 指針指向的節點。

運行結果

三，兩兩交互鏈表中的節點

3.1 題目分析

說來慚愧，這道題當時寫的時候基本沒有什麼思路，結果還是看了題解才寫出來的。

現在想想這真是道靈魂題啊，真是沒想到還能用遞歸去寫這道題，不得不說真是萬能的遞歸啊（主要本人太菜，哈哈）。

遞歸的方式在於如果是偶數鏈表，將兩兩節點相互交換；如果是奇數鏈表，那最後一個節點保持不動，下面用 debug 調試會看的清楚些。

將在偶數位上的節點指向上一個奇數位的節點，使用遞歸依次類推來遍歷整個鏈表。

大致的思路是這樣，使用遞歸將鏈表遍歷結束，然後返回最後節點【4】並指向上一個節點【3】；接著返回遞歸的結果【2】指向上一個節點【1】，而節點【1】也是指向節點【4】。

接著下次遞歸

按照規則分析，節點【4】與節點【3】交換位置，那返回的就是節點【4】

現在回到第一步遞歸的結果，當時 head 指向的節點【1】，那麼 head.next 指向誰？現在遞歸結果返回節點【4】，因此 head.next 也就指向的是節點【4】

最後節點【1】與節點【2】交換位置，就成了最後的鏈表交換結果。

這樣分析還是很抽象，下面用 debug 調試走一遍就清晰了。

3.2 程式碼分析

遞歸的程式碼還是比較簡單，先貼上來。

public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode nextNode = head.next;
        head.next = swapPairs(nextNode.next);
        nextNode.next = head;
        return nextNode;
    }