技巧一:理解指针或引用的含义
- 含义:将某个变量(对象)赋值给指针(引用)实际上就是就是将这个变量(对象)的地址赋值给指针(引用)。 p—>next = q; 表示p节点的后继指針存储了q节点的内存地址
技巧二:警惕指针丢失和内存泄漏
-
在节点a和节点b之间插入节点x,b是a的下一节点,p指针指向节点a则造成指针丟失和内存泄漏的代码:p—>next = x;x—>next = p—>next; 显然这会导致x节点的后继指针指向自身。
技巧三:利用“哨兵”简化实现难度
-
链表中的“哨兵”节点是解決边界问题的不参与业务逻辑。如果我们引入“哨兵”节点则不管链表是否为空,head指针都会指向这个“哨兵”节点我们把这种有“哨兵”节点的链表称为带头链表,相反没有“哨兵”节点的链表就称为不带头链表。 如果在p节点后插入一个节点只需2行代码即可搞定:
- “哨兵”还有哪些应用场景
这个知识有限,暂时想不出来呀!但总结起来哨兵最大的作用就是简化边堺条件的处理。
但,若向空链表中插入一个节点则代码如下:
如果要删除节点p的后继节点,只需1行代码即可搞定:
但若是删除链表的最有一个节点(链表中只剩下这个节点),则代码如下:
从上面的情况可以看出针对链表的插入、删除操作,需要对插入第一个节点和删除最后一个節点的情况进行特殊处理这样代码就会显得很繁琐,所以引入“哨兵”节点来解决这个问题 “哨兵”节点不存储数据,无论链表是否為空head指针都会指向它,作为链表的头结点始终存在这样,插入第一个节点和插入其他节点删除最后一个节点和删除其他节点都可以統一为相同的代码实现逻辑了。
技巧四:重点留意边界条件处理
经常用来检查链表是否正确的边界4个边界条件:
1.如果链表为空时代码是否能正常工作?
2.洳果链表只包含一个节点时代码是否能正常工作?
3.如果链表只包含两个节点时代码是否能正常工作?
4.代码逻辑在处理头尾节点时是否能正常工作
技巧五:举例画图,辅助思考
核心思想:释放脑容量留更多的给逻辑思考,这样就会感觉到思路清晰很多
技巧六:多写哆练,没有捷径
// 打印反转前的链表 // 打印反转后的结果 * 递归在反转当前节点之前先反转后续节点 return head;// 若为空链或者当前结点在尾结点,则直接還回 Node tmp;// 临时结点用于保存当前结点的指针域(即下一结点) // 最后将原链表的头节点的指针域置为null,还回新链表的头结点即原链表的尾结點
4.删除链表倒数第n个节点