链表算法题之中等级别，debug调试更简单

原创

杨小鑫

修改于 2021-03-04 17:54:18

3300

修改于 2021-03-04 17:54:18

文章被收录于专栏：公众号【小样编程】公众号【小样编程】

文章简述

大家好，本篇是个人的第 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;
    }