leetCode 刷题经验总结二   2022-01-22


这是刷 leetCode 的第二篇博文, 涉及到的题目:
A) 移除链表中的元素(编号: 203): leetcode-cn.com/problems/remove-linked-list-elements/
B) 设计链表(编号:707): leetcode-cn.com/problems/design-linked-list/
C) 反转链表(编号:206) : leetcode-cn.com/problems/reverse-linked-list/
D) 查找环形链表的入口节点(编号:142): leetcode-cn.com/problems/linked-list-cycle-ii/

过程记录

A) 移除链表中的元素:

给定一个值和一个链表的 head 节点, 查找链表中的所有节点, 如果节点中的值等于给定的值, 则删除该节点, 剩余的节点组成一个链表, 最后返回该链表。

这道题很容易做, 但总觉得如果下次做的也一样会出错, 为什么呢? 因为我们需要考虑空链表的情况, 只有一个节点的链表的情况, 以及循环到尾节点时的边界判断等问题, 我用了两个指针, 一个用来表示当前节点, 另一个用来表示下一个节点，那么多细节, 怎么记得了?

很显然, 这个记不住的。

完成后我就看了看别人的题解, 一下子豁然开朗, 我们需要做的是, 在链表的前面加入一个虚拟节点, 这样当我们循环的时候, 就不用顾虑那么多了, 直接循环就是了！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public ListNode removeElements(ListNode head, int val) {
        ListNode tempNode = new ListNode();
        tempNode.next = head;
        ListNode curNode = tempNode;

        while(curNode != null && curNode.next != null) {
            if (curNode.next.val == val) {
                curNode.next = curNode.next.next; 
				// curNode = curNode.next.next;
            } else {
                curNode = curNode.next;
            }
        }

        return tempNode.next;
    }

这里有一个细节需要注意:
当我们删除节点的时候, 我们只需要将当前节点指向下一个节点的下一个节点就可以了, 我们不需要将当前节点移动到下一个节点, 

1
// curNode = curNode.next.next;

也就是上面注释掉的语句我们不需要了, 做这个是多余的, 因为循环后他会自动移动到下一个节点， 我们多谢这条语句, 增加的记忆的负担。

B) 设计链表

设计一个类, 实现链表的功能:

  1. 在头节点插入一个节点(addAtHead)
  2. 在尾节点插入一个节点(addAtTail)
  3. 在指定的位置插入一个节点(addAtIndex)
  4. 获取指定位置的节点(get)
  5. 删除一个节点(remove)

说起来也搞笑, 我在设计这个链表的时候, 把它设计成了 ArrayList, 底层是数组实现, 设计完成后一看, 时间和内存空间的性能打败了80-90%的人, 心里面沾沾自喜, 等到后面回过头来看的时候才知道到自己搞错了, 题目要求设计链表, 不是使用数组啊, 再看别人的题解, 才知道, 能够打败80-90%的用户, 原来是有原因的。

笑话就说到这里了, 下面进入正题.
实际上, addAtHead, addAtTail， 都是 addAtIndex, 可是我刚开始的时候, 却没有这么做, 代码看起来非常的混乱，虽然功能也能够实现, 但需要调试很久才能实现, 有几点需要注意:

  1. 涉及到链表, 我们应该在头部添加虚拟节点, 操作起来会非常的方便
  2. 添加了虚拟节点了以后, 我们就不需要考虑空链表的情况了, 因为已经存在虚拟节点了
  3. 关于链表的长度, 添加节点和删除节点都需要修改。 这里想得出经验性的总结: 有添加动作就应该有删除的动作, 这是成对出现的, 成对出现的动作, 在其中一个方法体内所做的任何修改, 凡是涉及到成员变量的, 我们都要成对的修改。我自己就忽略了这个问题, 添加节点的时候, 链表长度增加了, 但是删除的时候忘记了减少的动作, 结果在获取节点的时候就下标越界了, 而且 debug 的时候, 还以为是获取的方法出现了问题, 这个过程是非常耗时的。
  4. 设计之前应该做个思考, 哪些地方的功能是有共性的， 有共性的话我们把它抽出来, 添加节点的功能, 这样代码简洁。
C) 反转链表

给定一个链表, 对链表中的所有节点重新排序, 让顺序颠倒过来, 然后返回完成后的链表。

这个链表实现起来慢简单地, 我就老老实实的遍历一遍, 把所有的节点存放到 List 中, 然后再从List的底部遍历到头部, 就这样实现了。

可是话说到底, 简单的东西, 往往不是最容易想到的, 这个功能其实遍历一遍就够了， 采用双指针的办法, 一个指针指向前面的节点, 另外一个指针指向当前节点, 把当前节点指向前面的节点后, 就可以向后面移动了, 一直遍历到末尾节点, 功能上就实现了。

需要注意的一点就是, 把原来的头部节点的下一个节点设置为 null 以防止形成循环链表。

D) 查找环形链表的入口节点

什么是环形链表?
链表中的头部节点一直连接到尾部节点, 然后尾部节点又连接到前面的某个节点, 就这样形成了循环。

之前看到<编程原本>里面有介绍这个环形链表, 只需要使用快跑慢跑的方法就可以知道链表是否是环形, 这个方法简单来说就是让A和B两个人在赛道上跑步, B 的速度比 A 的速度快一倍, 如果赛道是环形的, B跑完一圈后最终会追上A。

但我记不住入口点的计算公式, 所以采用标记法, 从头开始遍历, 一个节点一个节点记录下来, 同时进行比较, 如果下次再找到同一个节点, 那这个节点就是入口节点了。

那么, 快跑慢跑的方法呢? 如何记住那个公式? 我看了官网给出的解题思路, 他的描述如下:
当快跑的人和慢跑的人相遇时, 我们再指定第三个人从头部节点开始跑, 速度跟慢跑的人一样, 最终慢跑的人和第三人会在入口节点相遇。

总结

  1. 链表需要引入头部虚拟节点, 操作起来方便
  2. 凡是成对出现的动作, 涉及到成员变量的, 我们都要成对的修改成员变量的值
  3. 反转链表只需要遍历一遍就可以了, 需要使用两个指针, 把当前节点指向前一个节点。
  4. 环形链表, 采用快跑慢跑的方式, 需要引入第三人, 并且第三人和慢跑的人用相同的速度一起跑, 最终会在入口点相遇。
  5. 敲代码前得思考, 有没有共性? 能不能抽象?

分享到:


  如果您觉得这篇文章对您的学习很有帮助, 请您也分享它, 让它能再次帮助到更多的需要学习的人. 您的支持将鼓励我继续创作 !
本文基于署名4.0国际许可协议发布，转载请保留本文署名和文章链接。 如您有任何授权方面的协商，请邮件联系我。

Contents

  1. 过程记录
    1. A) 移除链表中的元素:
    2. B) 设计链表
    3. C) 反转链表
    4. D) 查找环形链表的入口节点
  • 总结