带你新学期领跑！8000字吐血总结数据结构之单链表

是用来碎的

单链表详解

• 一、前言
  
• 二、什么是链表？
  
• 
  
  
  
  • 
    
    
    
    • 2.1、链表的概念：
      
    • 2.2、两种重要的单链表
      
    • 2.3、关于单链表的一些基础知识
      
      
    
    
  
• 三、单链表的实现
  
• 
  
  
  
  • 
    
    
    
    • 3.1、穷举法创建一个简单的链表
      
    • 3.2、遍历链表
      
    • 3.3、得到链表的长度
      
    • 3.4、头插法
      
    • 3.5、尾插法
      
    • 3.6、 任意位置插入节点
      
    • 3.7、查找是否包含关键字key是否在单链表当中
      
    • 3.8、删除全部节点
      
    • 3.9、删除第一次出现关键字为key的节点
      
    • 3.10、删除全部值为key的节点
      
      
    
    
  
• 四、LeetCode和剑指Offer上的单链外貌试题
  
• 五、其他练习题
  

一、前言

在上篇文章中，我们详细的讲解了顺序表，这里链接给大家放在下面。没看过的同学可以看一看，因为单链表就是在顺序表之上，做出优化的线性表。
新学期预习吗？保姆级讲解数据结构之顺序表的9个方法+手撕代码
大家还记得顺序表中的add方法吗？那写起来简直是一个贫苦，又要考虑pos下标是否正当，还得一个一个的把后面的元素移到前面，这样一来，不仅代码写起来贫苦，代码执行的时间复杂度也高。但也不是没有优点。

---

顺序表：由数组构成，那么它也就包含了数组的特性。
优点：
1、查询元素时非常方便快捷，可以通过一个下标，能够快速的找到当前的数据。O(1).
缺点：
1、每次都会浪费大小不等的内存，假设当前数组大小为20；假如你要放第21个元素的时候，就需要扩容，假设扩容2倍后，大小是40，只放一个元素，那么剩下19个就浪费掉了。
2、每次扩容的时候，都需要拷贝数组的内容，拷贝的过程中也是需要时间的，造成一定程度资源的浪费。
3、删除和插入数据的时候，都需要移动数据。
那么题目来了，有没有一种表，又不浪费内存，删除、插入数据的时候还方便快捷呢？

---

这时候能够办理上面三个题目的链表来了！
二、什么是链表？

2.1、链表的概念：

链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。

2.2、链表的分类：链表的结构非常多样化，根据带头和不带头，双向和单向，循环和不循环可以组成很多种链表。

随便链表的种类有很多，但是只需要重点掌握两种即可。

---

2.2、两种重要的单链表

1、无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试口试中出现很多。

1、无头双向循环链表：在Java聚集框架当中，LinkedList的底层就是由这种链表实现的。

注意：每个链表的400、200、300均为节点的引用地址，实际上是以16进制的方式存储的，这里我为了绘图方便，进行了简写。

---

2.3、关于单链表的一些基础知识

1、链表在逻辑上是连续的，但是物理上不一定是连续的。这里的物理上，指的是内存地址上。
2、单链表的值域：
对于单链表来说，每一个节点都3个属性，在下图中最上面的123，指的是当前节点的地址(本来应该是16进制，这里为了方便说明用10进制)。val域：val是value的缩写，就是值的意思，这里存放的是当前节点需要存储的信息。
next域：它的范例是一个节点范例。由于单链表在逻辑上是连续的，故对于一个节点来说，它不仅需要存放自己的val值，它还需要存放自己的下一个节点的地址->next，以此来实现逻辑上的连续。

3、单链表的结构
头节点+数据节点

---

三、单链表的实现

光说不练假把式，我们相识了链表的结构、用处。现在我们来亲手实现一个自己的单链表。
3.1、穷举法创建一个简单的链表

这里我先用穷举的方式一一创建节点，这样方便理解，下文再报告用其他方法创建链表

1. public class MylinkedList {
2.     public  ListNode head;//标识这个链表的头
3.     /**
4.      * 穷举法，最简单的方式把链表一个一个列举出来。
5.       */
6.     public  void createList(){
7.         ListNode listNode1=new ListNode(12);
8.         ListNode listNode2=new ListNode(13);
9.         ListNode listNode3=new ListNode(23);
10.         ListNode listNode4=new ListNode(33);
11.         ListNode listNode5=new ListNode(44);
12.         listNode1.next=listNode2;
13.         listNode2.next=listNode3;
14.         listNode3.next=listNode4;
15.         listNode4.next=listNode5;
16.         //head引用 引用的是listNode1引用 引用的对象
17.         this.head=listNode1;
19.     }
20. }
21. class ListNode{
22.    public  int val;//值
23.    public ListNode next;//储存下一个节点的地址，它是一个引用
25.     /**
26.      * 不带参数的构造方法
27.      */
28.     public  ListNode(){
30.     }
31.     /**
32.      * 带一个参数的构造方法
33.      */
34.     public  ListNode(int val){
35.        this.val=val;
36.    }
37. }

复制代码

---

现在链表有了，那么题目来了，数组可以通过for循环的方式遍历链表，大概直接通过数组下标找到某个节点，那如何遍历链表当中的每个元素呢？

先看这样一行代码：

1. head=head.next;

复制代码

大家都知道head代表的是头结点的一个引用。这行代实际上是在修改引用，那把head修改到哪里呢？next指的是当前节点的下一个节点的地址，那么head.next意思就是head的下一个节点，这行代码就是让head走到它下一个节点的位置。现在它走到了listNode2的位置。

接下来再看这样一行代码

1. head=head.next.next

复制代码

聪明如你，假如当前head是listNode2，那么head.next就是listNode3的地址就指的是234，它后面再加一个next，就再指向在一个地址就是了。以是它的意思是让从listNode2走到listNode4的位置。

慢慢的我们发现，我们可以通过head=head.next的方式让head这个引用不停的指向下一个节点，这岂非不就是在遍历链表吗？我们让head走头开始，每走过一个节点，打印一个节点对应的val值。直到走到最后一个节点。
接下来我们来实现这个方法。

---

3.2、遍历链表

上面我们已经知道了遍历链表的方式是让head一直等于head.next。我们假如需要遍历整个链表，就需要给他加一个限制条件。考虑到head具有特别的含义，我们这里用一个cur节点来遍历链表。this.head=!null

1. /**
2.      *遍历链表
3.      *
4.      */
5.     public  void disPlay(){
6.         ListNode cur=this.head;
7.        while (cur!=null){
8.            /**
9.             * 注意不能while循环的判断条件不能写成
10.             * this.head.next!=null。
11.             * 这样的话，最后一个节点是不能被打印的
12.             *
13.             */
14.            System.out.println(this.head.val);
15.            cur=cur.next;
16.        }
17.           System.out.println();
18.     }

复制代码

总结：假如想遍历完链表，一定得是cur！==null，这样才算是遍历完了。
有了上面的基础，接下来我们在实现一些更复杂的方法。

---

3.3、得到链表的长度

思路是遍历一遍链表，界说一个计数器count，每遍历一个节点就让count+1,遍历完成后，返回count的值就是链表的长度了。
上代码！

1. //得到单链表的长度
2.     public int size(){
3.         int count=0;
4.         ListNode cur=this.head;
5.         while (cur!=null){
6.             count++;
7.             cur=cur.next;
8.         }
9.         return count;
10.     }

复制代码

size方法和display方法差异在多了一个计数器，在同样遍历遍历的基础下，display方法是打印链表的val值，而size方法是让计数器count+1.

---

3.4、头插法

1、刚刚我们以穷举法这样的方式创建了一个链表，现在我们用头插法创建链表。
对于两种链表，两种不同的头插法方式。
（1）：对于无头单向链表。

用蓝色字体的Node节点是需要头插的节点，它当前的val值是110，地址是777，next域是null。对于没有头结点的链表，头插法就是直接把需要插入的节点放到当前链表的第一个位置即可。
如图：

对于单向有头链表头插法就需要把插入的元素放到head节点和head下一个节点直接，因为有头的链表，head不能变。
如图：

上代码！

1.    //头插法   无头单向链表
2.     public void addFirst(int data){
3.    ListNode Node=new ListNode(data);
4.    Node.next=this.head;
5.    this.head=Node;
6.     }

复制代码

3.5、尾插法

尾插法顾名思义，和头插法相似，尾插法把需要插入的节点插入到链表的尾部即可。但是题目来了，头插法可以直接插是因为链表本来就有head节点，但是链表并没有特别指出尾巴在哪里。所为尾插法第一个要做的是就是找到链表的尾巴，然后在插入到最后。修改next。
1、找尾巴：找尾巴照旧和size方法类似，界说一个cur节点，让他一直遍历，直到cur.next==null，就找到尾巴了。这时制止循环，不然就指向下一个节点。

2、修改next：找到尾巴之后，让cur.next=Node就好。让链表原本的尾巴，指向现在的Node节点。

3、另有一件事：万一链表是空的呢？那就是第一次插入了，这时直接让head=node就好。
上代码！

1.    //尾插法
2.     public void addLast(int data){
3.         ListNode node=new ListNode(data);
4.         //第一次和不是第一次
5.         if(this.head==null){
6.             this.head=node;
7.         }
8.         else {
9.             ListNode cur=this.head;
10.             while (cur.next!=null){
11.                 cur=cur.next;
12.             }
13.             cur.next=node;
14.         }
15.     }

复制代码

---

3.6、 任意位置插入节点

这个方法的意思就是在某一个位置，插入一个节点。第一个数据节点为0号下标，以此类推。

这时，需要修改的域有，上一个节点的next域，因为插入后它的next域就应当是当前插入节点的地址了，另有就是当前节点的next域，把它的next域修改成原本3号下标节点的地址。以下是插入的步骤和特别情况处理。
我们先相处一个基础版的代码：

1. node.next=cur.next;
2. cur.next=node;

复制代码

0、index位置小于0大概比链表长度还大怎么办？
1、需要找到插入位置的前一个节点的地址，在上图是需要先找到1号下标节点的地址。
2、0位置可没有前一个节点。
3、要插入到最后一个节点怎么做？
这些题目，都会在代码中办理。
4、找到index下标前一个节点的方法 findInddexSubOne
让一个引用从头开始，走index-1步，这是这个引用指向的就是前一个节点。

1.    /**
2.      * 让一个引用从头开始，走index-1步
3.      * @param index
4.      * @return
5.      */
6.     public  ListNode findInddexSubOne(int index){
7.        int count=0;
8.        ListNode cur=this.head;
9.        while (count!=index-1){
10.            cur=cur.next;
11.            count++;
12.        }
13.        return  cur;
15.     }

复制代码

整个方法代码如下：
它有点长，你忍一下。

1.     //任意位置插入,第一个数据节点为0号下标    public void  addIndex(int index,int data){        //1、判断index是否正当        if(indexsize()){            System.out.println("index位置不正当");            return;        }        //2、index为0，直接头插法           if(index==0){               addFirst(data);               return;           }        //3、index==size()，直接尾插法           if(index==size()){               addLast(data);               return;           }        /**         * 4、正常的情况         *  cur指向的是一个index-1位置的节点         */        ListNode cur=findInddexSubOne(index);        ListNode node=new ListNode(data);        node.next=cur.next;        cur.next=node;    }    /**
2.      * 让一个引用从头开始，走index-1步
3.      * @param index
4.      * @return
5.      */
6.     public  ListNode findInddexSubOne(int index){
7.        int count=0;
8.        ListNode cur=this.head;
9.        while (count!=index-1){
10.            cur=cur.next;
11.            count++;
12.        }
13.        return  cur;
15.     }

复制代码

---

3.7、查找是否包含关键字key是否在单链表当中

遍历链表，界说一个cur引用，从链表的头开始，假如cur的val值和key相等了，就返回true，假如遍历完了，还没有找到，那就是没有，返回false。
方法代码如下：

1.     //查找是否包含关键字key是否在单链表当中
2.     public boolean contains(int key){
3.         ListNode cur=this.head;
4.         while (cur!=null){
5.             if(cur.val==key){
6.               return  true;
7.             }
8.         }
9.         
10. return  false;
11.     }

复制代码

---

3.8、删除全部节点

由于链表是都 next域一个个毗连起来的，那么删除以是节点的一个粗暴的方法就是把全部的next置空，让每个节点都找不到下一个节点，这样链表就毗连不起来，就算是删除了。
第一次尝试：我们试试是否可以像之前遍历链表一样，将每次颠末的cur节点置空它的next域，这样就把整个链表删完了。

  但是当我们实际操作的时候发现，当你将cur节点的next域删除的时候，那它要怎么找到下一个节点呢？

我们在界说一个节点curNext保存cur下一个节点就是了。这样每次删除的时候，curNext还可以指向下一个节点。删除完之后再让cur指向curNext。

另有一件事！
节点另有头结点没有删除，以是当循环走完，我们还需要让head节点置空，这样就是真正的把全部节点删除了。

---

上代码！

1.   //删除所有节点
2.     public void clear(){
3.         ListNode cur=this.head;
4.         while (cur!=null){
5.             ListNode curNext=cur.next;
6.             cur.next=null;
7.             cur=curNext;
8.         }
9.         this.head=null;
10.     }

复制代码

---

3.9、删除第一次出现关键字为key的节点

假设要删除的节点是6，下标为del，我们只需要找到它的前驱节点prev，直接让这个前驱节点和del的下一个节点相连，就变向的忽略的del节点，这就算是删除这个这点了。
总结：
1、找到待删除节点的前驱节点和下一个节点
2、将前驱节点的next域指向待删除节点的next域。
3、有一种特别情况是头结点是需要删除的节点。那么直接置空就好。

具体细节都在代码中，找到前驱节点我写成了一个方法search在下面的代码中

1.     //找到前序节点 服务于  删除第一次出现关键字为key的节点
2.     public  ListNode searchPrev(int key){
3.         ListNode prev=this.head;
4.         while (prev!=null){
5.             if(prev.next.val==key){
6.                 return  prev;
7.             }
8.             prev=prev.next;
9.         }
10.         return  null; //找完了都没返回，说明没有找到这个节点。
11.     }

复制代码

删除方法

1. //删除第一次出现关键字为key的节点
2.     public void remove(int key){
3.     //0、头结点是要删除的节点
5.         if(this.head.val==key){
6.             this.head=this.head.next;
7.             return;
8.         }
9.     //1、找到要删除节点的前驱节点
10.     ListNode prev=searchPrev(key);
11.         if(prev==null){
12.             System.out.println("没有你要删除的节点");
13.             return;
15.         }
16.     //2、开始删除节点
17.       ListNode del=prev.next;
18.         prev.next=del.next;
19.     }

复制代码

---

3.10、删除全部值为key的节点

1、上面我们已经写了9个方法了，相信大家单链表已经掌握的不错了，这是最后一个方法。我们这次将难度上升到口试的高度！ 在只遍历链表一遍的情况下，删除全部值为key的节点。

---

如下图，有两个val值为45的节点，我们这个方法需要只遍历链表一遍，就删除这两个val值为45的节点。

思路：
1.界说cur为当前要删除的节点，prev为删除节点的前驱节点，每次判断cur.val是否等于key，假如等于key就把prev.next指向cur.next。假如不相等，就让cur和prev一起向后走。

上代码

1.   //删除所有值为key的节点
2.     public void removeAllKey(int key){
3.        ListNode prev=this.head;
4.        ListNode cur=this.head.next;
5.        while (cur!=null){
6.            if(cur.val==key){
7.                prev.next=cur.next;
8.                cur=cur.next;
9.            }
10.            else {
11.                prev=cur;
12.                cur=cur.next;
13.            }
14.        }
15.        //别忘了头结点
16.        if(this.head.val==key){
17.            this.head=this.head.next;
18.        }
19.     }

复制代码

只遍历一遍就完成了删除以是val值等于key的节点。你真棒!

四、LeetCode和剑指Offer上的单链外貌试题

上面学习完了，怎么创建一个自己单链表，并且完成了单链表的10个方法，现在来试试挑战口试题把。题解在下方，加油哦！
剑指 Offer II 021. 删除链表的倒数第 n 个结点
LeetCode 24：两两互换链表中的节点、1662. 检查两个字符串数组是否相等
leetcode 21. 归并两个有序链表
五、其他练习题

我还总结了一些LeetCode和剑指offer的题解，一起来看看吧！。
剑指 Offer 67. 把字符串转换成整数
怎么把i am a student逆置成student a am i？口试题逆置字符串讲解
三种方法任君挑选 LeetCode_136只出现一次的数字
什么？动态规划10行求出连续子数组的最大和 剑指offer-42讲解
剑指 Offer 39. 数组中出现次数凌驾一半的数字 简单易懂14行搞定 。大家皆可会
二叉树的层序遍历原理+LeetCode真题练习
剑指 Offer 58 - II. 左旋转字符串的三种解法一起看看吧！！
字符串“aabcccccaaa”压缩成“a2b1c5a3“还要返回更小的？力扣口试题 01.06. 字符串压缩讲解
字符串bit666keji123“中数字的个数？
找到不重复的数字进阶版 空间复杂度O(1),时间O(n)平方，不能修改数组内容。不能对数组进行排序
LeetCode_231. 判断一个数是否为2 的幂，与运算一行代码办理
验证尼科彻斯定理，即：任何一个整数m的立方都可以写成m个连续奇数之和

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！