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

语言: CN / TW / HK

文章简述

大家好,本篇是个人的第 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;
    }
3.3 debug 调试
第一步,节点【1】和节点【2】

开始进入递归循环,此时 nextNode 节点为【2】,那该节点的下一个节点为【3】

第二步,节点【3】和节点【4】

现在 nextNode 节点为【4】,再次进入递归循环时,节点【4】的 next 就为 null,因为节点【4】为最后一个节点,开始结束递归。

现在开始返回递归的结果,首先返回的就是节点【3】和节点【4】

再看第 43 行代码,将节点【4】下一个节点指向了节点【3】,并返回了节点【4】

接着返回节点【1】和节点【2】

注意:上一步递归中,我们返回的结果为节点【4】

上图中看到 head 节点为【1】,而 head.next 也就是节点【4】了

最后返回交换后的节点【1】

3.4 小补充

还记得上面我们说的,如果链表为奇数,最后结果如何呢?

现在接着上面的 debug 看下最后奇数的节点怎么返回。

假设现在新增一个节点【5】

按照 if 判断,节点【5】为最后一个节点,进入 if 判断后就将节点【5】返回。

还记得我们上面说的 head.next 指针吗,它指向的是递归返回的结果,我们最后一次递归的时候,head 不就是节点【3】吗!

当节点【3】和节点【4】交换后,节点【3】不就正好指向了返回的节点【5】

四,总结

解决链表相关的题目,我们大多可以使用双指针(快慢指针),数组,递归,迭代这 4 种方式。

在做完简单题目后,再加上本篇文章的 3 道中等题目,使用双指针,递归就可解决大多数的题目。后面将中等题目刷完后,再来看看链表题目有多少是可以用上述几种方式去解决。

最后,求关注

原创不易,每一篇都是用心在写。如果对您有帮助,就请一键三连(关注,点赞,再转发)

我是杨小鑫,坚持写作,分享更多有意义的文章。

感谢您的阅读,期待与您相识!

分享到: