【数据结构 Java 版】玩转链表（1）单链表+链表面试题

我不是女神ヾ 2021-09-13 19:56 278阅读 0赞

### 文章目录 ###

*   *  一、链表
     *   *  1. 概念
         *  2. 结构
     *  二、单向不带头非循环链表
     *   *  1. 概念及结构
         *  2. 链表的实现
     *  三、链表面试题
     *  四、总结

## 一、链表 ##

### 1. 概念 ###

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

上章介绍到顺序表适合用作查询和修改，而不适合用作插入和删除。并且它增容时容易造成空间浪费。而链表则具有以下的特点

>  *  适合用作插入和删除
>  *  随用随取，避免了空间的浪费
>  *  不适合用作查询和修改

### 2. 结构 ###

链表其实可以想象成一条被打了一些结的绳子

![在这里插入图片描述][f83f0033f8034ac2a2cf973c38339147.jpg_pic_center]

而实际上，链表就是由一个个节点构成的，只不过每个节点一般有两个域

>  *  **数值域 data：** 里面存储数据
>  *  **next 域：** 里面存储的是下一个节点的地址（是引用变量）

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

其中

>  *  **尾节点：** 当这个节点的 next 域为 null 时，该节点就是尾节点
>  *  **头节点：** 整个链表的第一个节点就是头节点

实际中的链表结构非常多，通过以下的情况的组合可以有**8种**链表的结构（比如带头单向循环链表就是一种）

>  *  单向、双向
>  *  带头节点、不带头节点
>  *  循环、非循环

而上图所示，就是一个单向不带头非循环链表。

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

可能有人会疑问，上述图片中不是存在头节点吗？那为啥它又是一个不带头节点的链表呢？我将上述图片实例稍稍改一下就是带头节点的了![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZCe5ZCe5ZCQ5ZCQ5aSn6a2U546L_size_18_color_FFFFFF_t_70_g_se_x_16_pic_center]

我在原有的头节点前面又多了一个节点，并且这个节点的数值域里面的数据可有可无，因为对其没有影响。而这里面的**头节点只是一个标志，标识这个节点是该链表的头**

那带头节点的和不带头结点的链表有啥差别呢？

>  *  **不带头：** 这个链表的头节点可能发生改变
>  *  **带头：** 这个链表的头节点不会发生改变

那循环链表又是啥样的呢？我们可以将上述单向不带头非循环链表稍微修改一下![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZCe5ZCe5ZCQ5ZCQ5aSn6a2U546L_size_14_color_FFFFFF_t_70_g_se_x_16_pic_center 1]

即将尾节点的 next 域存储了头节点的地址

我们知道一个节点一般就两个域，但如果是双向链表，则就有三个域了

>  *  **数值域 data：** 里面存储数据
>  *  **next 域：** 里面存储的是下一个节点的地址（是引用变量）
>  *  **prev 域：** 里面存储的是上一个节点的地址（是引用变量）

我们画一个不带头双向非循环链表就是这样的![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZCe5ZCe5ZCQ5ZCQ5aSn6a2U546L_size_14_color_FFFFFF_t_70_g_se_x_16_pic_center 2]

接下来我将主要介绍**单向不带头非循环链表**和**双向不带头非循环链表**，这两种链表也是经常出现在面试题中的

## 二、单向不带头非循环链表 ##

### 1. 概念及结构 ###

上述通过图解，大家应该对单向不带头非循环链表应该有了了解。那么代码中该怎么实现呢？

我们知道，链表应该可以看作一个类，而节点本身其实也可以抽象的看作成一个类

首先对于节点类，代码可以写出这样

class Node{ 
        public int val;
        public Node next;
        public Node(int val){ 
            this.val=val;
        }
    }

先定义了数值域，再定义了 next 域（由于 next 存储的是下一个节点的地址，故写出上述那样）。而我们初始时可以知道 val，所以可以写个构造函数对 val 进行初始化，而该节点的 next 域初始时是不可能知道的，所以不对 next 做初始化

如果创造一个 Node 对象就可以写出

Node node = new Node(10);

即头节点的数值域为10。

再定义链表类，代码可以写成这样

public class MyLinkedList { 
        public Node head;
    }

我们定义了一个头节点，这是我们很容易发现的，就比如我要对该链表进行头插，则该链表的头节点一直都在改变。所以写上述的代码就是为了标识单链表的头节点。

### 2. 链表的实现 ###

接下来我们来实现单向不带头非循环链表的一些操作

1.  打印链表
    
        public void display(){ 
            Node cur =this.head;
            while(cur!=null){ 
                System.out.print(cur.val + " ");
                cur=cur.next;
            }
            System.out.println();
        }
2.  求链表的长度
    
        public int size(){ 
            Node cur=this.head;
            int count=0;
            while(cur!=null){ 
                count++;
                cur=cur.next;
            }
            return count;
        }
3.  查找值 key 是否在单链表中
    
        public boolean contains(int key){ 
            Node cur=this.head;
            while(cur!=null){ 
                if(key==cur.val){ 
                    return true;
                }
                cur=cur.next;
            }
            return false;
        }
4.  清除单链表
    
        public void clear(){ 
        	while(this.head!=null){ 
             	Node curNext=this.head.next;
             	this.head.next=null;
             	this.head=curNext;
        	}
        }
    
    > 当一个节点不被引用时，Java 中的垃圾回收器将会自动对它回收
5.  头插法
    
        public void addFirst(int data){ 
            Node node=new Node(data);
            if(head==null){ 
                this.head=node;
            }else { 
                node.next = this.head;
                this.head = node;
            }
        }
6.  尾插法
    
        public void addLast(int data){ 
            Node node = new Node(data);
            if(this.head==null){ 
                this.head=node;
            }else { 
                Node cur = this.head;
                while (cur.next != null) { 
                    cur = cur.next;
                }
                cur.next = node;
            }
        }
7.  通过下标找到前驱节点（第一个节点下标为0）
    
        public Node searchPrev(int index){ 
            Node cur = this.head;
            int count=0;
            while(count!=index-1){ 
                cur=cur.next;
                count++;
            }
            return cur;
        }
8.  任意位置插入
    
        public void addIndex(int index, int data){ 
            if(index<0 || index>size()){ 
                throw new RuntimeException("index 不合法");
            }
            if(index==0){ 
                addFirst(data);
                return;
            }
            if(index==size()) { 
                addLast(data);
                return;
            }
            Node node =new Node(data);
            Node cur =searchPrev(index);
            node.next=cur.next;
            cur.next=node;
        }
9.  通过值 key 找到前驱节点（第一个节点下标为0）
    
        public Node searchPrevNode(int key){ 
            Node cur = this.head;
            while(cur.next!=null){ 
                if(cur.next.val==key) { 
                    return cur;
                }
                cur=cur.next;
            }
            return null;
        }
10. 删除第一次出现的值为 key 的节点
    
        public void remove(int key){ 
            if(this.head==null){ 
                return;
            }
            if(key==this.head.val){ 
                this.head=this.head.next;
                return;
            }
            Node node = searchPrevNode(key);
            if(node==null){ 
                System.out.println("链表中无要删除的元素");
            }else { 
                node.next = node.next.next;
            }
        }
11. 删除所有出现的值为 key 的节点
    
        public void removeAllKey(int key){ 
            if(this.head==null){ 
                return;
            }
            Node prev=this.head;
            Node cur=this.head.next;
            while(cur!=null){ 
                if(cur.val==key){ 
                    cur=cur.next;
                    prev.next=cur;
                }else{ 
                    prev=cur;
                    cur=cur.next;
                }
            }
            if(this.head.val==key){ 
                this.head=this.head.next;
            }
        }

呼，写的我人傻了

![在这里插入图片描述][1b54ccf327f6492aba3b9f8053ec26e8.jpg_pic_center]

你以为结束了吗？NO！下面还有一大波链表面试题等着我和你，冲吧，牛牛！

## 三、链表面试题 ##

1.  删除链表中等于给定值 val 的所有节点 [OJ 链接][OJ]
2.  反转一个单链表 [OJ 链接][OJ 1]
3.  给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点 [OJ 链接][OJ 2]
4.  输入一个链表，输出该链表中倒数第k个结点 [OJ 链接][OJ 3]
5.  将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的 [OJ 链接][OJ 4]
6.  编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前 [OJ 链接][OJ 5]
7.  在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针 [OJ 链接][OJ 6]
8.  链表的回文结构 [OJ 链接][OJ 7]
9.  输入两个链表，找出它们的第一个公共结点 [OJ 链接][OJ 8]
10. 给定一个链表，判断链表中是否有环 [OJ 链接][OJ 9]
11. 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null [OJ 链接][OJ 10]
12. 如果你已经可以轻松应对上述题目了，可以继续去下面的链接中做题 [Leetcode OJ 链接][Leetcode OJ] 和 [牛客 OJ 链接][OJ 11]

## 四、总结 ##

今天简单了解了链表，以及对单向不带头非循环链表做了一些基操的实现。下章将包含个人的上述前11道 OJ 题的题解，以及了解双向不带头非循环链表

[f83f0033f8034ac2a2cf973c38339147.jpg_pic_center]: /images/20210913/162d9fcc4edb496ab81b68c9dfbf6695.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZCe5ZCe5ZCQ5ZCQ5aSn6a2U546L_size_14_color_FFFFFF_t_70_g_se_x_16_pic_center]: /images/20210913/c41c2e59f8964dd395d73e454b513402.png
[4ef639a0b4b5449f9f040dfc64897807.png_pic_center]: /images/20210913/77e1e51295054b49b2ec0a35510b3ee0.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZCe5ZCe5ZCQ5ZCQ5aSn6a2U546L_size_18_color_FFFFFF_t_70_g_se_x_16_pic_center]: /images/20210913/0e34fce248f84aab9653dee15605760b.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZCe5ZCe5ZCQ5ZCQ5aSn6a2U546L_size_14_color_FFFFFF_t_70_g_se_x_16_pic_center 1]: /images/20210913/118e28310d504726b79fd5425bc38fec.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZCe5ZCe5ZCQ5ZCQ5aSn6a2U546L_size_14_color_FFFFFF_t_70_g_se_x_16_pic_center 2]: /images/20210913/d7edf9f1cfb646bca9097f15d75dd4d0.png
[1b54ccf327f6492aba3b9f8053ec26e8.jpg_pic_center]: /images/20210913/41cbd217436644ff9e06ec1d9d8a7465.png
[OJ]: https://leetcode-cn.com/problems/remove-linked-list-elements/description/
[OJ 1]: https://leetcode-cn.com/problems/reverse-linked-list/description/
[OJ 2]: https://leetcode-cn.com/problems/middle-of-the-linked-list/description/
[OJ 3]: https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&&tqId=11167&rp=2&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking
[OJ 4]: https://leetcode-cn.com/problems/merge-two-sorted-lists/description/
[OJ 5]: https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking
[OJ 6]: https://www.nowcoder.com/practice/fc533c45b73a41b0b44ccba763f866ef?tpId=13&&tqId=11209&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking
[OJ 7]: https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa?tpId=49&&tqId=29370&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking
[OJ 8]: https://leetcode-cn.com/problems/intersection-of-two-linked-lists/description/
[OJ 9]: https://leetcode-cn.com/problems/linked-list-cycle/description/
[OJ 10]: https://leetcode-cn.com/problems/linked-list-cycle-ii/description/
[Leetcode OJ]: https://leetcode-cn.com/tag/linked-list/problemset/
[OJ 11]: https://www.nowcoder.com/activity/oj?title=%E9%93%BE%E8%A1%A8&page=1