04_链表（下）

04_链表（下）

在Java语言中没有指针的概念，其体现是“引用”。

引用：将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针，或者反过来说，指针中存储了这个变量的内存地址，指向这个变量，通过指针就能找到这个变量。

在链表中插入数据或者删除数据时，千万要注意指针的指向，一个不留神，就会造成指针的丢失，前后段不能相连。

如图所示，我们希望在结点a和相邻的结点b之间插入结点x，假设当前指针p指向结点a。如果我们将代码实现变成下面这个样子，就会发生指针丢失和内存泄露。

p-next = x; // 将p的next指针指向x结点；
x-next = p-next; // 将x的结点的next指针指向b结点；

这样操作就会导致b后面的数据全部丢失。

正确方式：

x-next = p-next; // 将x的结点的next指针指向b结点；
p-next = x; // 将p的next指针指向x结点；

即，千万要注意操作的先后顺序。

对于单链表来说，由于链表的头尾结点特殊性，针对链表的插入、删除操作，需要对插入第一个结点和删除最后一个结点的情况进行特殊处理。

如：在结点p后面新增加一个结点，

本来：

new_node-next = p-next;
p-next = new_node;

如果是头结点，则要先进行判断：

if (head == null) {
 head = new_node;
}

如：删除最后一个结点，

本来：

p - next = p - next - next;

如果是尾结点：

if (head-next == null) {
  head = null;
}

为了使得代码更加优雅，哨兵就要登场了。哨兵，解决的是国家之间的边界问题。同理，这里说的哨兵也是解决“边界问题”的，不直接参与业务逻辑。

我们引入哨兵结点，在任何时候，不管链表是不是空，head指针都会一直指向这个哨兵结点。我们也把这种有哨兵结点的链表叫带头链表。相反，没有哨兵结点的链表就叫作不带头链表。

我画了一个带头链表，你可以发现，哨兵结点是不存储数据的。因为哨兵结点一直存在，所以插入第一个结点和插入其他结点，删除最后一个结点和删除其他结点，都可以统一为相同的代码实现逻辑了。

检查链表代码是否正确的边界条件：

当链表为空时，代码是否能正常工作。

当链表只包含一个结点时，代码是否能正常工作。

当链表只包含两个结点时，代码是否能正常工作。

代码运行处理链表头尾结点时，能否正常工作。

对于复杂的指针操作，借助画图来辅助。

手写代码，多调试几遍，孰能生巧

leetcode推荐题目：

单链表反转

链表中环的检测

两个有序链表的合并

删除链表倒数第n个结点

球链表的中间结点

04_链表（下） 相关文章

1. leetcode：面试题 02.04. 分割链表（中等，链表）
   

   leetcode：面试题 02.04. 分割链表（中等，链表） 自己想出来了： 分成两个链表，分别是大于x和小于x的。然后合并 这里用到了一个很好的思路： 创建空的链表的时候，记得new来开辟空间。 数据水，没有进行比x大的元素还要提前...

2. 04_链表简介
   

   04_链表简介 一、链表介绍 链表是有序的链表，但它在内存中存储方式如下图所示： 小结： 链表是以 节点方式，链式存储 的； 每个节点包含data域（ 保存数据 ）、next域（ 保存指向下一个节点的信息 ）； 如上图，我们发现链...

3. 每天一道Code 面试题 04.03. 特定深度节点链表
   

   每天一道Code 面试题 04.03. 特定深度节点链表 代码思路 简单层次遍历。 代码 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }

4. 剑指leetcode面试题 04.03. 特定深度节点链表
   

   剑指leetcode面试题 04.03. 特定深度节点链表 题目描述：给定一棵二叉树，设计一个算法，创建含有某一深度上所有节点的链表（比如，若一棵树的深度为 D，则会创建出 D个链表）。返回一个包含所有深度的链表的数组。 方法...

5. LeetCode | 面试题 04.03. 特定深度节点链表【Python】
   

   问题 力扣 给定一棵二叉树，设计一个算法，创建含有某一深度上所有节点的链表（比如，若一棵树的深度为 D，则会创建出 D 个链表）。返回一个包含所有深度的链表的数组。 示例： 输入：[1,2,3,4,5,null,7,8] 1 / \ 2 3 / \ \ 4 5 7 / 8...

6. leetcode 章节分类 树 面试题 04.03 特定深度节点链表
   

   leetcode 章节分类 树 面试题 04.03 特定深度节点链表 将一个二叉树层次遍历，返回一个用数组存储的链表。 没什么其他方法，直接上层次遍历代码就行。 /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * Tr

7. caffe框架下添加自己的MFC程序（下）（2016-08-04 ）
   

   caffe框架下添加自己的MFC程序（下）（2016-08-04 ） 转自：http://blog.csdn.net/shakevincent/article/details/52116388 版权声明：本文为博主原创文章，未经博主允许不得转载。 5：添加人脸分类程序 无法识别using namespace cafffe: 解决方案： 发现c...

8. ubuntu16.04深度学习环境搭建二：ubuntu16.04下安装anaconda
   

   ubuntu16.04深度学习环境搭建二：ubuntu16.04下安装anaconda 由于tensorflow暂不支持python3.7版本，但之前安装的anaconda默认安装python3.7，经过各种切换python版本的操作失败后，决定卸载之前的anaconda，重新安装带python3.6的anaconda版本 anaconda...

9. 『Windows10Pro下+Vmware15.5.2下+Ubuntu20.04下+Docker下安装Ub
   

   Windows10Pro下+Vmware15.5.2下+Ubuntu20.04下+Docker下安装Ubuntu20.04 Update Ubuntu 20.04 System To make sure, all the repositories and installed packages are up to date just run a simple updater command for that, also make sure you have roo

10. 如何在 Ubuntu 13.04 和 12.04 下安装 KDE SC 4.11
    

    经过开发团队六个月的紧张工作后，KDE 4.11 SC 发布了，这是一个长期支持版本，所以在两年内你可以放心使用。而开发团队将有两年的开发时间来做 KDE Framework 5 和 Qt 5。新版本带来的诸多改进和新功能就不多说了，大家可以看...

11. JS笔记04-对象（下）
    

    JS笔记04-对象（下） 【JS面向对象三大特征：封装、继承、多态】 封装：就是把抽象出的属性和对属性的操作封装在一起,属性被保护在内部,程序的其它部分只有通过被授权的操作(函数),才能对属性进行操作。简单地说，就是把...

12. Ubuntu server16.04下配置JAVA及TOMCAT
    

    Ubuntu server16.04下配置JAVA及TOMCAT 在Ubuntu server16.04LTS中配置Java及Tomcat，一堆坑

13. Ubuntu18.04 下修改 root密码
    

    Ubuntu18.04 下修改 root密码 首先打开终端输入命令 sudo passwd root 然后依次是当前用户密码，将要设置root密码，确认root密码。切换root看一下 备注： #符号 是系统用户 root $符号 是你创建的用户 没指定权限！

14. Anaconda在Ubuntu16.04下安装
    

    Anaconda在Ubuntu16.04下安装 因为需要下载ONNX，所以来下载Anaconda，一开始以为是下载conda，结果官网上推荐下载Anaconda,，里面集成了conda和python等多个科学包，使用起来更加方便，感觉唯一缺点就是太占内存。下面记录一下安装的过...

15. VMware下安装Ubuntu18.04
    

    VMware下安装Ubuntu18.04 请先下载Ubuntu18.04 Ubuntu18.04下载，请记住下载的目录，之后安装需要 虚拟机环境配置 1、第一步新建虚拟机，选择推荐，点下一步 2、勾选第三项，稍后安装操作系统，点下一步 3、选择linux，选择虚拟机地址...

16. Ubuntu 18.04系统下创建新用户
    

    Ubuntu 18.04系统下创建新用户 以下介绍在Ubuntu 18.04系统下创建新用户/目录、修改用户权限及删除用户的正确方法。在Ubuntu系统上创建新用户使用[sudo useradd 用户名]命令，但只能创建用户，不能在/home/中创建用户目录，也无法设置...

17. Ubuntu14.04下安装Anaconda
    

    Ubuntu14.04下安装Anaconda 在Ubuntu14.04下安装Anaconda的步骤： Step 1. 下载Anaconda 选择linux版本64-Bit(x86)Installer(525MB) ，保存在linux系统的下载目录下。 下载地址： https://www.anaconda.com/download/ Step 2. 安装Anaconda Ctrl+Alt+T快捷键

18. Ubuntu20.04下深度学习环境配置
    

    Ubuntu20.04下深度学习环境配置 Ubuntu下深度学习环境配置 Ubuntu下深度学习环境配置 一、换国内源 二、gpu驱动 三、Anaconda安装 四、pytorch安装 五、cuda安装 六、cudnn安装 Ubuntu下深度学习环境配置 这篇文章记录了我在配置深度学习环...

19. C语言 在合并编译 ( 多.c文件 ) 情况下 实现 linked list ( 链表
    

    C语言 在合并编译 ( 多.c文件 ) 情况下 实现 linked list ( 链表 ) Chapter 1. Stage12.写main和node.h 本节是对 linked list 的编写进行预备，实现 main 函数的初步编写，并定义node的结构和引用 linked list 的结构 ?本人是初学C语言编程，dalao 发现...

20. ubuntu16.04下进行android开发
    

    ubuntu16.04下进行android开发 ubuntu16.04下进行android开发 在linux环境下进行android开发，android开发环境的搭建是相当重要的，但是这一步也是最麻烦的。 还好，我们有ADT Bundle来帮忙。 这里贴出linux版本的ADT Bundle的百度云下载链接： 32...