马上2021年了线性表你还不知道原理？给老王整的明明白白

冷不防 2022-12-04 03:24 169阅读 0赞

### 文章目录 ###

*  一、线性表必知必懂的原理
 *   *  （一）线性表通俗易懂原理
 *  二、线性表对数据的操作
 *   *  （一）增加操作（老王插队神操作）
     *  （二）删除操作（小明取完票让位给老王）
     *  （三）查找操作
 *  三、单链表案例
 *   *  （一）案例1：反转链表
     *   *  1、题目描述
         *  
         *  2、解题思路
         *  3、解题代码
     *  （二）案例2：找出链表的中间节点
     *   *  1、题目描述
         *  2、解题思路
         *  3、解题代码
     *  （三）案例3：判断链表是否有环
     *   *  1、题目描述
         *  2、解题思路
         *  3、解题代码
 *  四、链表总结

# 一、线性表必知必懂的原理 #

## （一）线性表通俗易懂原理 ##

线性表是n个数据元素的有限序列，最常用的是`链式表达`，通常也叫做`线性链表或者链表`在链表中存储的数据元素也叫做`结点`，一个结点存储的就是一条`数据记录`。

每个结点的结构包括两个部分：

*  1、具体的数据值；
 *  2、指向下一个结点的指针。

![在这里插入图片描述][20200905160934839.png_pic_center]

在链表的最后一个结点，通常会有个头指针用来指向第一个结点

![在这里插入图片描述][2020090516094628.png_pic_center]

对于链表的最后一个结点，由于在它之后没有下一个结点，因此它的指针是个`空指针`

假如：小明，小张，小李和小郑在排队卖鸡翅，但是排队就是讲究先来先买的原则，不能插队。小明再购买鸡翅付钱的时候突然没钱了，假设小明和小郑认识，小明需要找到小郑借钱来付上买鸡翅的钱。。。那么小明想要找到小郑，就需要先找到他的下一个结点，一看不是小郑，就继续下一个结点，直到找到为止。

![在这里插入图片描述][20200905160957787.png_pic_center]

小明是可以找到小郑的，但是小郑就无法找到小明了，也就是说`单链表`反过来查找是不行的，也被称之为`单向链表`。

为了弥补`单向链表的不足`，我们可以对单向链表进行改造：

> 对于单向链表，把最后一个元素的指针指向第一个元素，就得到了`循环链表`。
> 
> 这样小郑就可以查找他自己的next结点，就可以找到小明或者小李等。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE3NjIzMzYz_size_16_color_FFFFFF_t_70_pic_center]

由于单向链表一个结点只有指向下一个结点的指针，可以想象一下，是不是也可以修改成每个结点也指向上一个结点，是不是就可以找到自己上一个结点的数据了呢。

> 我们再增加一个指向上一个结点的指针，这样就得到了`双向链表`

![在这里插入图片描述][20200905161019859.png_pic_center]

当然了，还有更好的办法，那就是把`循环链表`和`双向链表`进行`结合`就得到了`双向循环链表`。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE3NjIzMzYz_size_16_color_FFFFFF_t_70_pic_center 1]

不管是循环链表还是双向链表，还是双向循环链表，都是在单向链表的基础上加以改造得到的，改造后的链表在操作某种数据的时候可以提高一定的效率，所以单向链表是基础。

# 二、线性表对数据的操作 #

对数据的操作无非就是对数据的`增删改查`。只是不同的结构有着不同的处理逻辑罢了。

## （一）增加操作（老王插队神操作） ##

小明、小张、小李、小郑在排着队`取票`，突然来了一个老王，老王非常的着急，因为老王马上就要到火车发车的时间了，只好插队了，此时老王跟后面所有的排队的人都打了个招呼，然后大家也都同意他插队进去，那么老王就先去取票了，我们忽略打招呼的过程，`重点放在如何插队`。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE3NjIzMzYz_size_16_color_FFFFFF_t_70_pic_center 2]

我们先不管如何插入到链表中的，`先看图说话`。

> **`老王如果想插队必定插入到小明的后面，因为老王在插队的过程中小明此时可能会正在取票呢。`**

那么插入老王后的数据就是：

![在这里插入图片描述][20200905161059298.png_pic_center]

整个插入操作也非常的简单，只需要让老王的next指向小张，然后小明再指向老王就ok了。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE3NjIzMzYz_size_16_color_FFFFFF_t_70_pic_center 3]

**思考一下？？？？**

反过来操作可以吗?

让`小明先指向老王`，`老王的next指向小张`。

可以吗？

答案是不可以的，这样的话，`小明先指向老王`之后，小张以及小张之后的数据会全部丢失的。不信你看：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE3NjIzMzYz_size_16_color_FFFFFF_t_70_pic_center 4]

代码如下：

newNode.next = head.next
    head.next = newNode

## （二）删除操作（小明取完票让位给老王） ##

老王要想取到票，还欠一点火候，欠什么呢？需要等待小明取完票，然后离开才可以的。

那么就需要小明离开这个链表，我们通常说删除小明这个结点。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE3NjIzMzYz_size_16_color_FFFFFF_t_70_pic_center 5]

删除操作也比较简单，只需要把前一个结点指向后面的后面的这个结点就ok了。

代码：(直接就可以忽略小明这个结点)

head.next=head.next.next;

## （三）查找操作 ##

查找操作我们通常会查两种，第一种是按照位置的序号，第二种是按照值来查找。

例如：

*  查找第3个位置的是谁；
 *  查找小张是否还在排队。

在链表中的查找功能是比较弱的，对于链表中的查找，唯一的办法就是一个挨着一个的遍历去对比，对比较着去查找。

时间复杂度也就是O(N)。

# 三、单链表案例 #

## （一）案例1：反转链表 ##

### 1、题目描述 ###

反转一个单链表。

示例:

`输入: 1->2->3->4->5->NULL`  
`输出: 5->4->3->2->1->NULL`

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/reverse-linked-list  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

###  ###

--------------------

### 2、解题思路 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE3NjIzMzYz_size_16_color_FFFFFF_t_70_pic_center 6]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE3NjIzMzYz_size_16_color_FFFFFF_t_70_pic_center 7]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE3NjIzMzYz_size_16_color_FFFFFF_t_70_pic_center 8]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE3NjIzMzYz_size_16_color_FFFFFF_t_70_pic_center 9]

### 3、解题代码 ###

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
    class Solution { 
        public ListNode reverseList(ListNode head) { 
              
            if(head==null)
                return head;
    
            //定义三个指针暂存后面的或者前面的结点，防止丢失。
            ListNode curr,prev,next;
            curr=head;
            prev=next=null;
    
            while(curr!=null){ 
                next = curr.next;
                curr.next = prev;
                prev=curr;
                curr=next;
            }
    
            return prev;       
        }
    }

如果不明白，可以自己画图来试试。

## （二）案例2：找出链表的中间节点 ##

### 1、题目描述 ###

[876. 链表的中间结点][876.]

难度简单256收藏分享切换为英文关注反馈

给定一个带有头结点 `head` 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

**示例 1：**

输入：[1,2,3,4,5]
    输出：此列表中的结点 3 (序列化形式：[3,4,5])
    返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
    注意，我们返回了一个 ListNode 类型的对象 ans，这样：
    ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

**示例 2：**

输入：[1,2,3,4,5,6]
    输出：此列表中的结点 4 (序列化形式：[4,5,6])
    由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

**提示：**

*  给定链表的结点数介于 `1` 和 `100` 之间。

[https://leetcode-cn.com/problems/middle-of-the-linked-list/][876.]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE3NjIzMzYz_size_16_color_FFFFFF_t_70_pic_center 10]

### 2、解题思路 ###

思路很简单，就是利用两个指针来完成，一个走的比较快的，一个走的比较慢的。

每次快的走2个（next.next），每次慢的走1个节点（next）。

当快等于null时（next.next=null时），停止；

当快的next不为空时，返回慢的next节点。

当快的next为空时，返回慢的当前节点。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE3NjIzMzYz_size_16_color_FFFFFF_t_70_pic_center 11]

### 3、解题代码 ###

//找出链表中间节点
        static public ListNode middleNode(ListNode head) { 
    
            if(head==null)
                return head;
            ListNode fast,//快
                    slow;//慢
            fast=slow=head;
    
            while (fast!=null && fast.next!=null && fast.next.next!=null){ 
                fast = fast.next.next;
                slow = slow.next;
            }
    
            if(fast.next!=null)
                return slow.next;
    
            return slow;
        }

## （三）案例3：判断链表是否有环 ##

### 1、题目描述 ###

[141. 环形链表][141.]

难度简单738收藏分享切换为英文关注反馈

给定一个链表，判断链表中是否有环。

为了表示给定链表中的环，我们使用整数 `pos` 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 `pos` 是 `-1`，则在该链表中没有环。

**示例 1：**

输入：head = [3,2,0,-4], pos = 1
    输出：true
    解释：链表中有一个环，其尾部连接到第二个节点。

![在这里插入图片描述][2020090516140934.png_pic_center]

**示例 2：**

输入：head = [1,2], pos = 0
    输出：true
    解释：链表中有一个环，其尾部连接到第一个节点。

![在这里插入图片描述][20200905161419135.png_pic_center]

**示例 3：**

输入：head = [1], pos = -1
    输出：false
    解释：链表中没有环。

![在这里插入图片描述][20200905161429578.png_pic_center]

**进阶：**

你能用 *O(1)*（即，常量）内存解决此问题吗？

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE3NjIzMzYz_size_16_color_FFFFFF_t_70_pic_center 12]

### 2、解题思路 ###

此题也是可以利用快慢指针来完成的，同样，快指针一次走两步，慢指针一次走一步，如果有环的话，快和慢两个指针早晚会相遇的。那么如果快指针的val等于慢指针的val那么直接返回true即可。

### 3、解题代码 ###

/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */
    public class Solution { 
        public boolean hasCycle(ListNode head) { 
             if(head==null)
                return false;
    
            ListNode fast,slow;
            fast=slow=head;
            while (fast!=null && fast.next!=null && fast.next.next!=null){ 
                fast=fast.next.next;
                slow=slow.next;
                if(fast.val==slow.val)
                    return true;
            }
    
            return false;
        }
    }

# 四、链表总结 #

`链表对数据的存储方式是按照顺序的存储。`

--------------------

**什么时候用？**

>  *  当数据元素不确定时。
>  *  当需要经常进行数据的新增和删除时。

链表的反转、快慢指针是高效的操作链表的主要方法，是必须要掌握的内容。

[20200905160934839.png_pic_center]: /images/20221123/c17e63b43ddc49bea59a8037b0159aab.png
[2020090516094628.png_pic_center]: /images/20221123/ef853c79aaea41e08146c0e2090eda91.png
[20200905160957787.png_pic_center]: /images/20221123/f84b0cfe6a4940fb87260a24b9c074dc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE3NjIzMzYz_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/a6ed270da07f42f5a13b289b619e338c.png
[20200905161019859.png_pic_center]: /images/20221123/173ade9d22294c0c9e67707a3c376cf8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE3NjIzMzYz_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/861b0899eec24657a30e9a3075ca5437.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE3NjIzMzYz_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/4e966174f9554f62925eb176e3ba8df5.png
[20200905161059298.png_pic_center]: /images/20221123/cbf86691dbc04cb3bac754dac0cff819.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE3NjIzMzYz_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/1f6eb95bd608439a912b4cec28eb4cb5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE3NjIzMzYz_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221123/fdc9bbea707e4d598d616caee37968ad.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE3NjIzMzYz_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221123/a4df690686354c06b600e348602a73b0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE3NjIzMzYz_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221123/65754b89d2ec43f7891699b68e3ce847.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE3NjIzMzYz_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20221123/4dd0e02389894f04ac20e395ae20861c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE3NjIzMzYz_size_16_color_FFFFFF_t_70_pic_center 8]: /images/20221123/4d8e26c22bf74604a0ab0e2bc6ad4371.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE3NjIzMzYz_size_16_color_FFFFFF_t_70_pic_center 9]: /images/20221123/ed635c53c6304998aeb2efccb2fe258f.png
[876.]: https://leetcode-cn.com/problems/middle-of-the-linked-list/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE3NjIzMzYz_size_16_color_FFFFFF_t_70_pic_center 10]: /images/20221123/8aaff78519424676857a1810d0527d16.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE3NjIzMzYz_size_16_color_FFFFFF_t_70_pic_center 11]: /images/20221123/636c224ded724dadb1d75c53a122a6c0.png
[141.]: https://leetcode-cn.com/problems/linked-list-cycle/
[2020090516140934.png_pic_center]: /images/20221123/024770360edb4bc6b9156c5b32ac581b.png
[20200905161419135.png_pic_center]: /images/20221123/a870bb7e70024b85ad1756564e44d2c6.png
[20200905161429578.png_pic_center]: /images/20221123/c4513b6451a3472bb635daaf9f196984.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE3NjIzMzYz_size_16_color_FFFFFF_t_70_pic_center 12]: /images/20221123/5d1f436d429249659ff10dd713256035.png