JavaSE-10-顺序表和链表_顺序表按基准划分数据结构

1. 线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列，是一种在实际中广泛使用的数据结构，常见的线性表有：顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
数组形式储存

可以储存完，也可以有剩余空间

以链式结构储存

这是一个简单的单链表（单向无头非循环链表），具体的结构，后面我们会详细介绍。

2. 顺序表

2.1 概念及结构

数据结构： 描述+组织数据的方式。
顺序表就是一种数据结构，它的底层是一个数组。
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储，在数组上完成数据的增删查改。
为更好的理解顺序表，下图可以帮助更好的理解。

上面一行为存储数据的地方，而下面的则表示该链表里面数据的个数。

顺序表一般可以分为：

• 静态顺序表：使用定长数组存储。
• 动态顺序表：使用动态开辟的数组存储。

静态顺序表适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。
相比之下动态顺序表更灵活, 根据需要动态的分配空间大小。

2.2 接口实现

在上面，我们用图标示了顺序表，那么在 Java 当中，我们就要按照这样的思路来构造这些东西，让 JVM 知道我们所写的代码表示什么。
接下来我们将实现顺序表的接口，以下为代码：

import java.util.Arrays;

public class MyArrayList {
    public int[] elem;//存储数据的数组  引用类型(在堆上)
    public int usedSize;//有效数据的个数

    public MyArrayList() {//用构造方法对数组进行初始化
        this.elem = new int[5];//让this.elem等于新的整型数组
    }
}
1
2
3
4
5
6
7
8
9
10

-上面的代码中，我们首先创造了 elme ，它用来在堆上开辟空间，存储数组；
-紧接着我们创造力 usedSize，它用来记录顺序表里面有多少个数据。
-然后我们用构造方法对数组进行初始化，让数组可以存进顺序表里。

接口1：在顺序表的某个位置新增元素

//在pos位置新增元素
    public void add(int pos, int data) {
        //1.判断数组占满了没
        if (isFull()) {
            System.out.println("顺序表满了！需要扩容！");
            this.elem = Arrays.copyOf(this.elem,2*this.elem.length);//把扩容后的数组还是得赋值给原来的this.elem
            //return;
        }
        //2.先判断pos位置的合法性
        if (pos < 0 || pos > this.usedSize) {
            System.out.println("pos位置不合法！！！");
            return;
        }
        //3.从后往前挪元素，若pos==usedSize，则直接放到usedSize位置
        if (pos == this.usedSize) {
            this.elem[pos] = data;
            this.usedSize++;
            return;
        }
        for (int i = this.usedSize - 1; i >= pos; i--) {
            this.elem[i + 1] = this.elem[i];
        }
        this.elem[pos] = data;
        this.usedSize++;
    }
    public boolean isFull() {
        if (this.usedSize == this.elem.length) {
            return true;
        }
        return false;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

当我们在顺序表中添加元素的时候，可以将其填满，也可以有空位，当添加元素的个数大于它的空间的时候，可以扩容。在扩容以后，还是要把扩容后的表赋值回原来的表。

这样，我们的在顺序表中插入数据的接口就建立好了，为检验是否正确，我们还要创建一个打印的方法，以便检验插入的数据是否符合我们的设计思路。

注意：在顺序表中插入元素的时候，插入位置前面一定要有元素，否则不合法！！！

接口2：打印方法

// 打印顺序表
    public void display() {
        for (int i = 0; i < this.usedSize; i++) {
            System.out.print(this.elem[i]+" ");
        }
        System.out.println();
    }
1
2
3
4
5
6
7

打印的思路和之前打印数组里面的元素的思路一样。我们可以看到 usedSize 的引入，可以大大提高代码的效率，而不是重新再写代码去获取顺序表里面到底有多少个数据。
这两个准备做好以后，我们就可以在main 函数里面检验，我们是否正确插入了数据。

public static void main(String[] args) {
        MyArrayList myArrayList = new MyArrayList();
        myArrayList.add(0,1);
        myArrayList.add(1,2);
        myArrayList.add(2,3);
        myArrayList.add(3,4);
        myArrayList.display();
}
//输出：1,2,3,4
1
2
3
4
5
6
7
8
9

首先得实例化调用顺序表所在的类，由于顺序表里面储存的是数组，所以它的起始位置是从 0 开始的，这一点需要注意。

接口3：判断顺序表中是否包含某个元素

// 判定是否包含某个toFind元素
    public boolean contains(int toFind) {
        for (int i = 0; i < this.usedSize; i++) {
            if(this.elem[i] == toFind) {
                return true;
            }
        }
        return false;
    }
1
2
3
4
5
6
7
8
9

思路：利用 for 循环遍历顺序表。

接口4：查找某个元素对应的位置

// 查找某个元素对应的位置
    public int search(int toFind) {
        for (int i = 0; i < this.usedSize; i++) {
            if(this.elem[i] == toFind) {
                return i;
            }
        }
        return -1;
    }
1
2
3
4
5
6
7
8
9

思路：利用for循环遍历顺序表，如果找到，返回元素所在位置的下标，如果没有找到，则返回 -1，因为顺序表的下标和数组一样，默认是从 0 开始的。

接口5：获取某个位置的元素

//获取 pos 位置的元素
    public void getPos(int pos) {
        //1.判断顺序表是否为空
        if (isEmpty()) {
            return;
        }
        //2.pos不合法
        if (pos < 0 || pos >= this.usedSize) {
            System.out.println("pos位置不合法");
        }else {//3.返回那个位置的元素
            System.out.println(this.elem[pos]);
        }
    }
    public boolean isEmpty() {
        /*if(this.usedSize == 0) {
            return true;
        }
        return false;*/
        return this.usedSize == 0;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

思路：

• 首先得判断顺序表是不是空的；
• 接下来判断获取的位置是否符合我们创建的顺序表；
• 以上两个条件都合理的话，则可以直接返回该数据。

接口6：给某个位置设置元素

//pos 位置的元素设为 value
    public void updatePos(int pos, int value) {
        //1.判断顺序表是否为空
        if(this.isEmpty()) {
            return;
        }
        //2.pos不合法
        if(pos < 0 || pos >= this.usedSize) {
            return;
        }
        //3.设置值
        this.elem[pos] = value;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

思路：

• 首先还是得判断顺序表是否为空；
• 其次判断更新数据的位置的合法性；
• 上面两个条件都合理的话，就可以直接设置元素了。

接口7：删除第一次出现的关键字key

//删除第一次出现的关键字key
    public void remove(int key) {
        int index = search(key);//找到关键字，并且返回它的下标
        if(index == -1) {
            System.out.println("你要删除的关键字："+key+"不存在！！");
            return;
        }
        for (int i = index; i < this.usedSize-1; i++) {//挪的时候，i把最后一个数字挪完之后，不能再往后挪动了，因此得设置一个合理的条件i < this.usedSize-1
            this.elem[i] = this.elem[i+1];
        }
        this.usedSize--;
    }
1
2
3
4
5
6
7
8
9
10
11
12

思路：

• 首先，我们得借助接口4，找出这个关键字所在的位置；
• 其次判断位置的合法性；
• 最后直接把关键字后面的数据往前挪，则删除完成。同时，usedSize 这个数值也需要做相应的变化。

对于删除顺序表的数据，可以用下图理解：

其余接口：获取表的长度、清空顺序表

// 获取顺序表长度
    public int size() {
        return usedSize;
    }
    // 清空顺序表
    public void clear() {
        this.usedSize = 0;
    }
1
2
3
4
5
6
7
8

问题：

1. 顺序表的插入和删除，时间复杂度为O(N)
2. 增容需要申请新空间，拷贝数据，释放旧空间，会有不小的消耗。
3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。

基于以上缺点，我们引入了链表。

3. 链表

3.1 链表的概念及结构

链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。通俗的来讲链表就是一个个节点连接而成的。

链表的分类：
实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

• 单向、双向
• 带头、不带头
• 循环、非循环

接下来我们介绍一种单向不带头非循环链表，即单链表。
链表是由一个个节点连接而成的，节点的结构如下：

我们可以看到，一个节点有两个域，一个是数据，一个是地址，单链表就是由这样的节点连接而成的。

由上图我们可以看到：

• 单链表的每个节点有两个域，上半部分为数据，下半部分是指向下一个节点的引用（地址）；
• 第一个节点为头结点，最后一个节点是尾结点；
• 每一个节点的都是有引用（地址）的；
• 节点通过next 连接起来。

通过比较顺序表和链表的图的结构，我们可以看出：顺序表在物理上和逻辑上都是连续的；链表在物理上不一定连续，在逻辑上一定连续。

上面的图表示了一个无头的单链表，接下来我们看一个带头结点的单链表

它有头结点，但是头结点里面不存储数据。接下来的学习里面，我们先熟悉不带头的单链表，以此为基础，熟悉链表。

补充：
循环链表：

带环链表：

3.2 链表的实现

3.2.1 无头单向链表的实现

为了能够实现一个单链表，我们在代码中就要定义一个节点 Node ，它也是一个类，在这个类中，需要规定两个部分，一个是数据，另一个则代表下一个节点的地址；然后利用构造方法，给每一个节点的数据进行实例化。则代码可以写为：

//Node是一个类
class Node {//定义节点，它有两个值
    public int val;//整型数据
    public Node next;//下一个节点的地址

    public Node(int val) {
        this.val = val;
    }
}
1
2
3
4
5
6
7
8
9

然后我们紧接着创建一个链表的类，在它里面，我们可以调用节点的属性。
首先定义一个头结点，然后用枚举的方式给链表里面插入数据，代码如下：

public class MyLinkedList {//单链表
    public Node head = null;
    //利用穷举的方式创建一个单链表
    public void creatList() {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        this.head = node1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

在上述代码中，我们调用了 Node 这个类并且实例化出了 4 个对象，然后让每个对象的引用都指向下一个节点的引用，这样，节点和节点之间就连接起来了。

然后在 MyLinkedList 这个类中，为了检验链表的数据是否实例化成功，我们得创造一个打印函数：

接口1：打印函数

public void show() {
        /*while (this.head != null) {//该方法的缺点：最后head保存的值为null，即头不见了
            System.out.println(this.head.val);
            this.head = this.head.next;*/

        Node cur = this.head;//可保证head一直在前面。移动的只是cur
        while (cur != null) {
            System.out.print(cur.val+ " ");
            cur = cur.next;
        }
        System.out.println();
    }
1
2
3
4
5
6
7
8
9
10
11
12

打印函数可以写成上面两种，但优先推荐第二种。注释里面的打印函数，我们可以看到，是用 head 在遍历整个链表，链表遍历完之后，head 就在最后面的位置了，与我们设计的理念不符合。所以在下面的代码中，我们定义了一个新的节点 cur，让它代替头结点去遍历数组，这样，代码的合理性就提高了。

通过上面两个接口，我们可以完整的创建一个链表，但是方法太 low，如果链表中需要插入大量的数据，代码的效率就降低了，于是我们有了这样的方法来建立链表。即头插法：

接口2：头插法

顾名思义，头插法就是从链表的头部开始插入节点，那么每一个新插入的节点就是该链表的头结点。

//●头插法
    public void addFirst(int val) {
        Node node = new Node(val);//第一步,定义要插入的数据
        node.next = this.head;//第二步
        this.head = node;//可保证head不动
    }
1
2
3
4
5
6

我们已经在 MyLinkedList 这个类中定义好了头结点，因此在头插法的过程中，我们可以画图理解为：
第一步： 定义了头结点为空，插入的 node 节点定义了一个新的数据。

第二步： 让插入的 node 节点的 next 指向头结点，然后 head 等于node ，则新插入的第一个数据就是新链表的头结点了。

第三步： 继续插入新的数据

重复第二步的步骤，让插入的 node 的 next 等于头结点的地址，这样，两个节点因为这个地址连接在了一起，节点的指向是：从node 指向 head ，head 再等于 新插入的节点的地址，则新插入的节点就是新的链表的头结点。

之后插入的新节点只需重复第二步的步骤即可完成头插法。

接口3：尾插法

尾插法就是从链表的尾结点开始插入节点，而每一个新插入的节点就是新的链表的尾结点。

//●尾插法
    public void addLast(int val) {
        Node node = new Node(val);
        if(this.head == null) {//一个节点都没有的情况
            this.head = node;
        }else {
            Node cur = this.head;
            while (cur.next != null) {
                cur = cur.next;
            }
            //循环走到这里，cur.next == null;
            cur.next = node;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

首先我们考虑正常有多个节点的尾插法。

• 先定义一个 cur 代替 head 遍历链表，当 cur.next = null 的时候，相应的循环结束；
• 接着让走到目前尾结点处的 cur.next = 要插入的节点的地址。
• 特殊情况是：链表是空的，那么直接让 node 节点等于头节点即可。

接口4：任意位置插入

public Node searchIndexSubOne(int index) {//找到指定下标index处
        Node cur = this.head;
        /*while(index-1 != 0) {
            cur = cur.next;
            index--;
        }*/
        int count = 0;
        while (count != index - 1) {//判断移动的次数是否等于指定下标减一
            cur = cur.next;
            count++;
        }
        return cur;//挪到指定位置了
    }
    //●任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index,int data) {
        if(index < 0 || index > getLength()) {
            System.out.println("位置不合法！！");
            return;
        }
        if(index == 0) {
            addFirst(data);
            return;
        }
        if(index == getLength()) {
            addLast(data);
            return;
        }
        Node ret = searchIndexSubOne(index);
        //ret中存储的就是index-1位置处的节点的地址(引用)
        Node node = new Node(data);//设置插入的数据
        node.next = ret.next;//插入的数据的地址等于挪动到指定位置的地址
        ret.next = node;//挪动到指定位置的ret的地址就等于node的引用
    }
    public int getLength() {
        int len = 0;
        Node cur = this.head;
        while (cur != null) {
            len++;
            cur = cur.next;
        }
        return len;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

总体思路：在任意位置插入有以下情况：

• 在头结点处插入，相当于头插法；
• 在尾结点处插入，相当于尾插法；
• 在给定的位置插入，按照一定的方法找到插入的节点，再插入即可。

现在我们来讨论一下第三种情况：
要想在任意位置插入，我们就得找到这个位置，由图我们可以推断出，假设插入的位置是 index 为 2 的位置，则我们只需把 cur移动到 2 号位置的前一个节点，就可以保证新的节点能够连接起来，则 cur 与 index 的关系是：cur = index -1，我们可以利用循环，算出cur所移动的次数，然后找到 index ，这种情况下的插入即可简单完成。

接口5：查找链表中是否有要找的关键字

//●查找是否包含关键字key是否在单链表当中
    public boolean contains(int key) {
        Node cur = this.head;//通过Node定义一个cur等于头
        while(cur != null) {
            if(cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }
1
2
3
4
5
6
7
8
9
10
11

上面的接口实现了，对于这个接口的实现，是很简单的，只需遍历一次链表，就可以确定关键字是不是在链表中。

接口6：删除第一次出现关键字为 key 的节点

大体思路：要删除的节点不是头结点或尾结点的情况
如下图所示，假设我们要删除的是第三个节点，我们只需要找到要删除节点的前驱节点，直接让 cur.next 的值等于 最后一个节点的地址即可。

但是如何在只在遍历链表一遍的情况下，就能找到要删除的节点和它的前驱节点 cur？此时就需要写一个找前驱节点的方法，下面的代码很好理解。

//从头开始找key的前驱
    public Node searchPrev(int key) {
        Node cur = this.head;
        while(cur.next != null){
            if(cur.next.val == key) {//判断当前节点的下一个值等不等于key
                return cur;//如果等于，这个节点就是前驱
            }
            cur = cur.next;
        }
        //循环走完了,代表没有找到
        return null;
    }
    //●删除第一次出现关键字为key的节点
    public void remove(int key){
        //1.判断头节点是不是要删除的节点
        if(this.head.val == key) {//关键字等于head的时候
            this.head = this.head.next;//只需让head这个节点等于head.next的值
            return;
        }
        //2.找到key的前驱节点   找前驱节点的原因：如果删除的节点在链表中间，删除的节点没了以后，前驱节点的引用就要保证更改为删掉的数据的节点，这样，链表才算完整
        Node prev = searchPrev(key);
        if(prev == null) {
            System.out.println("没有要删除的这个节点！");
            return;
        }
        //找到指定的删除位置
        Node del = prev.next;//del是个节点
        //开始删除
        prev.next =del.next;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

整体思路：

• 先判断头结点是不是要删除的节点；
• 然后找到前驱节点；
• 接下来找到要删除的节点；
• 最后直接删除即可。

接口7：删除所有值为key的节点

思路：要删除节点，就得找到该节点的前驱节点。考虑有多个值需要删除的情况，也得考虑头结点为要删除的情况。cur 相当于要删除的节点。

//删除所有值为key的节点
    public void removeAllKey(int key) {
        Node cur = this.head.next;
        Node prev = this.head;
        //要把单链表的每个元素都遍历完
        while (cur != null) {
            if (cur.val == key) {
                //这是你要删除的节点
                prev.next = cur.next;
                cur = cur.next;
            }else {
                prev = cur;//或者prev = prev.next;
                cur = cur.next;
            }
        }
        if(this.head.val == key) {
            this.head =this.head.next;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

接口8：清空单链表

思路：可以直接让头结点为 null，也可以写一个循环，遍历链表的过程中，使每一个节点为空。还得考虑只有一个节点的情况。

public void clear() {
        //this.head = null;
        Node cur = this.head;
        while (cur != null) {
            Node curNext = cur.next;
            cur.next = null;
            cur = curNext;
        }
        this.head = null;//最后还要回收头结点
    }
1
2
3
4
5
6
7
8
9
10

3.2.2 无头双向链表的实现

无头双向链表和单链表相似，是由节点连接而成的，只不过，它的每个节点有三个域：第一个域表示当前节点的数字，第二个域表示当前节点的前驱节点的地址，第三个域表示下一个节点的地址。如下图，它的指向是这样的，这就是一个简单的无头双向链表。

要想实现无头双向链表，和单链表类似，创建一个 ListNode 的类，在这个类里面定义数据、前驱结点的地址、下一个节点的地址，再用构造方法给类的节点赋值：

class ListNode {
    public int val;
    public ListNode prev;
    public ListNode next;

    public ListNode(int val) {
        this.val = val;//指向
    }
}
1
2
3
4
5
6
7
8
9

接口1：打印函数

接下来创建一个 MyDoubleList 的类，用来表示无头双向链表，无头双向链表的所有接口都将在这个类里面实现

public class MyDoubleList {
    public ListNode head;//头
    public ListNode tail;//尾
    
    //打印方法
    public void display() {
        ListNode cur = this.head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

接口2：头插法

//头插法
    public void addFirst(int data) {
        ListNode node = new ListNode(data);
        if (this.head == null) {//第一次插
            this.head = node;
            this.tail = node;
        }else {
            node.next = this.head;
            this.head.prev = node;
            this.head = node;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12

接口3：尾插法

//尾插法
    public void addLast(int data) {
        ListNode node = new ListNode(data);
        if (head == null) {//第一次插入
            this.head = node;
            this.tail = node;
        }else {
            this.tail.next = node;
            node.prev = this.tail;
            this.tail = this.tail.next;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12

接口4：任意位置插入

//找到节点所在的下标
    public ListNode findIndex(int index) {
        ListNode cur = this.head;
        int count = 0;
        while (count != index) {
            cur = cur.next;
            count++;
        }
        return cur;
    }

    //任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index,int data) {
        if (index <0 || index >size()) {
            System.out.println("index不合法！！");
            return;
        }
        if (index == 0) {
            addFirst(data);
            return;
        }
        if (index == this.size()) {
            addLast(data);
            return;
        }
        ListNode cur = findIndex(index);
        ListNode node = new ListNode(data);
        node.next = cur;
        cur.prev.next = node;
        node.prev = cur.prev;
        cur.prev = node;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

接口5：查找关键字key是否在链表当中

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

接口6：删除第一次出现关键字为key的节点

//删除第一次出现关键字为key的节点
    public void remove(int key) {
        ListNode cur = this.head;
        while (cur != null) {
            if (cur.val == key) {
                if (this.head.val == key) {//删除的节点是头节点
                    this.head = this.head.next;
                    if (this.head != null) {//链表只有一个节点，且是需要被删除的
                        this.head.prev = null;
                    }else {
                        this.tail = null;
                    }
                }else {//中间和尾节点
                    if (cur.next != null) {//中间
                        cur.prev.next = cur.next;
                        cur.next.prev = cur.prev;
                    }else {//尾节点
                        cur.prev.next = cur.next;
                        tail = cur.prev;
                    }
                }
                return;
            }else {
                cur = cur.next;
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

接口7：删除所有值为key的节点

//删除所有值为key的节点
    public void removeAllKey(int key) {
        ListNode cur = this.head;
        while (cur != null) {
            if (cur.val == key) {
                if (this.head.val == key) {//删除的节点是头节点
                    this.head = this.head.next;
                    if (this.head != null) {//链表只有一个节点，且是需要被删除的
                        this.head.prev = null;
                    }else {
                        this.tail = null;
                    }
                }else {//中间和尾节点
                    if (cur.next != null) {//中间
                        cur.prev.next = cur.next;
                        cur.next.prev = cur.prev;
                    }else {//尾节点
                        cur.prev.next = cur.next;
                        tail = cur.prev;
                    }
                }
            }
            cur = cur.next;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

接口8：得到链表的长度

//得到链表的长度
    public int size() {
        int count = 0;
        ListNode cur = this.head;
        while (cur != null) {
            cur = cur.next;
            count++;
        }

        return count;
    }
1
2
3
4
5
6
7
8
9
10
11

接口9：清空链表

public void clear() {
        ListNode cur = this.head;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = null;
            cur.prev = null;
            cur = curNext;
        }
        this.head = null;
        this.tail = null;
    }
1
2
3
4
5
6
7
8
9
10
11

3.3 链表面试题

1. 删除链表中等于给定值 val 的所有节点

力扣题目：移除链表元素.
该题的代码和上面讲的接口7的代码一样，只不过在力扣上的时候需要判断：

if (head == null) return null;//链表一个节点都没有，则返回null，没有什么可以删除的
1

然后在代码的最后返回一个 head即可运行。

2. 反转单链表

力扣题目：反转一个单链表.

反转链表的意思是让节点逆置，即节点的指向倒着指向。如下图：

思路1：利用头插法，把原来链表后面的节点查到头结点前面。

/**
     * 给你单链表的头节点 head,请你反转链表，并返回反转后的链表。
     * 利用头插法
     * @return
     */
    public Node reverseList() {
        if (head == null ||this.head.next == null) {
            return this.head;
        }
        //cur代表的是当前要翻转或者头插的一个节点
        Node cur = this.head;
        Node curNext = cur.next;
        //处理头节点
        cur.next = null;
        cur = curNext;
        while(cur != null) {//用头插法
            curNext = cur.next;
            cur.next = this.head;
            this.head = cur;
            cur = curNext;
        }
        return this.head;
    }
    /**
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

思路2：定义一个前驱节点，代码如下：

/**
     * 给你单链表的头节点 head,请你反转链表，并返回反转后的链表。
     * 新的方法：定义一个前驱节点
     * @return
     */
    public Node reverseList1() {
        Node prev = null;
        Node cur = this.head;
        Node newHead = null;
        while (cur != null) {
            Node curNext = cur.next;
            if (curNext == null) {
                newHead = cur;
            }
            cur.next = prev;
            prev = cur;
            cur = curNext;
        }
        return newHead;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

由于 reverseList1( ) 类在编写时，定义了新的头结点，则检验的时候，需要调用新的 show2 方法：

//根据指定的节点位置开始打印（这个打印函数配合reverseList1()这个方法使用）
    public void show2(Node newHead) {
        Node cur = newHead;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
    }
1
2
3
4
5
6
7
8

3. 返回链表的中间节点

力扣题目：返回链表的中间节点.
题目描述：给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

思路：快慢节点 定义一个 fast ，每一次走两步，定义一个 slow 节点，每一次走一步，当 fast 或 fast.next 为 null 的时候，slow 所在的位置即为中间节点的位置，该思路适用于奇数节点和偶数节点。

/**
     * 给定一个头结点为 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点
     * @return
     */
    public Node middleNode() {
        Node fast = this.head;
        Node slow = this.head;

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

4. 输入一个链表，输出该链表中倒数第k个结点

牛客题目：输入一个链表，输出该链表中倒数第k个结点。.

思路：要输出倒数第 k 个节点，需要定义两个节点，fast 和 slow， fast 用循环的方法先走 k-1 步，然后 slow 和 fast 一起走，当 fast 或 fast.next 为 null 的时候，slow 所在的位置就是倒数第 k 个节点。

注意：判断 k 值的合理性；判断空链表的情况

/**
     * 输入一个链表，输出该链表中倒数第k个结点。
     * @param k
     * @return
     */
    public Node findKthToTail(int k) {
        if(k <= 0 || head == null) {
            return null;
        }
        Node fast = this.head;
        Node slow = this.head;
        while (k-1 != 0) {
            if (fast.next != null) {
                fast = fast.next;
                k--;
            }else {
                System.out.println("所给的k值太大了！！");
                return null;
            }
        }
        //到这里，fast走了k-1步
        while(fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

5. 链表分割

牛客题目：链表分割.
题目描述：编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前。

思路：如下图所示。一个有 5 个节点的单链表，假设给定的 x = 30，那么我们可以把比30小的数字插入到前面的一个线段上，把比30大的数字插入到后面的线段上，最后把两个线段再连接成一个链表即可。
注意： 按照上面的思路思考完成后，需要注意一些特殊情况。

• 1.首先得考虑在两部分的第一次插入和不是第一次插入的情况；
• 2.所有的数据都比规定的数据小，即所有的数据都插入到前半段，后半段是空的，反之亦然；
• 3.后半段的节点刚好只有一个，需要把该节点的 next 值置为 null，否则会造成死循环。

/**
     * 编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前,且不能改变原来的数据顺序，返回重新排列后的链表的头指针
     * @param x
     * @return
     */
    public Node partition(int x) {
        Node cur = this.head;
        Node bs = null;//bs是beforestart的缩写
        Node be = null;//bs是beforeend的缩写
        Node as = null;//afterstart
        Node ae = null;
        while (cur != null) {
            if (cur.val < x) {//小于x的
                if(bs == null) {//小于部分的第一次插入
                    bs = cur;
                    be = cur;
                }else {
                    be.next = cur;
                    be = be.next;
                }
            }else {//大于或等于x的
                if (as == null) {//大于部分的第一次插入
                    as = cur;
                    ae = cur;
                }else {
                    ae.next = cur;
                    ae = ae.next;
                }
            }
            cur = cur.next;
        }
        if (bs == null) {//这里判断如果x的值比链表当中的所有数字都要小
            return as;//返回后半段的头链表
        }
        be.next = as;//遍历完链表，将分开的两部分连起来
        if (as != null) {//最后一个数据是一个小于x的，被放到前半部分了，整个链表没有尾节点，就会进入死循环。
            ae.next = null;//ae和as刚开始的时候是在一起的，后面ae是移动的
        }
        return bs;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

6. 删除链表中重复的节点

牛客题目：删除链表中重复的节点.
题目描述：在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。

思路：定义一个 cur ，让它遍历链表；定义一个傀儡节点 tmpHead。先判断 cur.next != null && cur.val == cur.next.val 这个条件，然后让 tmpHead.next = cur；tmpHead = tmpHead.next；cur 继续往后遍历。当遇到重复数字的时候，写一个循环，让 cur 继续往后遍历，循环结束的时候， cur 所在的位置是相同的数字的最后一个，然后跳出循环，让 cur 再往后遍历一个节点，让此时的 cur.next 的值等于 tmpHead 这个节点，这样，链表就连接上了。

注意：

• 1.判断链表是否为空；
• 2.除头结点以外，其余节点的数字都相同，则需要注意把头结点的 next 值置为空。

/**
     * 在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。如,链表1->2->3->3->4->4->5 处理后为 1->2->5
     * @return
     */
    public Node deleteDuplication() {
        Node cur = this.head;
        Node tmpHead = new Node(-1);//定义一个傀儡节点，保证有一个节点是不动的。
        Node newHead = tmpHead;//这个考虑了从头节点开始就是一样的链表，只有尾节点不同的情况
        while (cur != null) {
            if (cur.next != null && cur.val == cur.next.val) {//找到重复的节点了
                while (cur.next != null && cur.val == cur.next.val) {
                    cur = cur.next;
                }
                cur = cur.next;
            }else {//没有找到重复的节点
                tmpHead.next = cur;
                tmpHead = tmpHead.next;
                cur = cur.next;
            }
        }
        tmpHead.next = null;//防止删除完了以后，只剩一个头结点
        return newHead.next;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

本题的难度稍微大一点，需要多多练习

7. 回文结构

牛客题目：链表的回文结构.
题目描述：对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。

思路：

• 先利用快慢节点找到当前链表的中间节点；
• 然后将后半部分链表反转；
• 反转的时候从slow 的下一个节点开始（对于偶数个节点也同样适用）。

注意考虑：奇数和偶数的节点情况

/**
     *对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构,
     *给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。
     *    测试样例：1->2->2->1
     *    返回：true
     * @return
     */
    public boolean chkPalindrome() {
        if (this.head == null) return false;//头节点为空
        if (this.head.next == null) return true;//只有一个节点
        Node fast = this.head;
        Node slow = this.head;
        while (fast != null && fast.next != null) {//用slow找到中间节点
            fast = fast.next.next;
            slow = slow.next;
        }
        Node cur = slow.next;
        while (cur != null) {//翻转后半部分链表
            Node curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }
        while (this.head != slow) {
            if (this.head.val != slow.val) {
                return false;
            }
            if (this.head.next == slow) {//节点数是偶数的情况
                return true;
            }
            this.head = this.head.next;
            slow = slow.next;
        }
        return true;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

8. 判断链表是否有环

力扣题目：给定一个链表，判断链表中是否有环.

思路：如下图。定义快慢节点，一个 fast 节点，一个 slow 节点。fast 每一次走两步，slow 一次走一步，当 fast 和 slow 再次相遇的时候，就说明该链表是有环的。

问：为什么 fast 只走两步，三步、四步不可以吗？
答：走两步可以保证最快相遇，三四步可能会错过好几次之后才相遇。

/**
     *  给定一个链表，判断链表中是否有环。
     * @return
     */
    public boolean hasCycle() {
        Node fast = this.head;
        Node slow = this.head;

        while (fast != null  &&  fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                return true;
            }
        }
        return false;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

9. 返回链表入环的第一个节点

力扣题目：返回链表入环的第一个节点.
题目描述： 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

思路：设置两个节点，fast 和 slow ，fast 每次走两步，slow 每次走一步。
假设在链表中，如下图，x 为入环前遍历的节点数，c 是环的长度，绿色部分是在环上相遇的点，它距离入环节点的距离为 y 。由于 fast 的速度是 slow 的二倍，那么，相遇时，路程也存在二倍关系。
相遇时：

• 慢节点 slow：x+c-y
• 快节点 fast：x+c+c-y

由上面的关系可以推出 x=y.

注意：相遇点不一定是环的入口点。

由于x=y，此时，我们将一个指针重新拉回到七点，之后两个指针一起走，当他们第一次相等时，该位置就是环的入口点。

/**
     * 给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null
     * @return
     */
    public Node detectCycle() {
        Node fast = this.head;
        Node slow = this.head;
        //这一步只是找到两个指针的相遇点。
        while (fast != null  &&  fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;//注意：这里在画图理解的时候，必须让slow 走完之后，如果两个节点相遇才算完
            if (fast == slow) {
                break;
            }
        }
        if (fast == null  ||  fast.next == null) {//审查一下，没有环的情况
            return null;
        }
        //接下来才是找环的入口点
        //令一个指针重新回到起点，之后两个指针同时走，再次相遇的点即为环的入口点。
        slow = this.head;
        while (fast != slow) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

10. 两个链表：合并两个有序链表

力扣题目：合并两个有序链表.

题目描述：将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

思路：由于我们无法确定两个节点哪一个头结点的数字较大，所以我们先定义一个傀儡节点 newH，让 tmpHead = newHead，让 tmpHead 代替 newHead 遍历两个链表。以下图为例：
定义好傀儡节点以后，经过判断得出 head1 的值小，则傀儡节点指向 head1 的头结点，head1 = head1.next，tmpHead = tmpHead.next，然后比较 head1 的第二个节点和 head2 的头结点的大小，以此类推。

在遍历过程中，将两个链表按照单链表的定义，将所有节点连接在一起，两个链表就合并成了一个有序的单链表。上图的步骤如下：

/**
     * 将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
     * @param head1 代表第一个单链表的头节点
     * @param head2 代表第一个单链表的头节点
     * @return
     */
    public static Node mergeTwoLists(Node head1, Node head2) {
        Node newHead = new Node(-1);//定义一个傀儡节点
        Node tmpHead = newHead;
        while (head1 != null  && head2 != null) {
            if (head1.val < head2.val) {
                tmpHead.next = head1;//指向
                head1 = head1.next;
                tmpHead = tmpHead.next;//往后移
            }else {
                tmpHead.next = head2;//指向
                head2 = head2.next;
                tmpHead = tmpHead.next;
            }
        }
        if (head1 != null) {//这种情况是一个链表遍历完了，另一个还没有完，直接指向没有遍历完的链表。
            tmpHead.next = head1;
        }
        if (head2 != null) {
            tmpHead.next = head2;
        }
        return newHead.next;
    }
   
   
    public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addLast(1);
        myLinkedList.addLast(3);
        myLinkedList.addLast(5);
        myLinkedList.addLast(7);
        myLinkedList.addLast(10);
        myLinkedList.show();

        MyLinkedList myLinkedList2 = new MyLinkedList();
        myLinkedList2.addLast(2);
        myLinkedList2.addLast(4);
        myLinkedList2.addLast(6);
        myLinkedList2.addLast(8);
        myLinkedList2.addLast(13);
        myLinkedList2.show();

        Node ret = mergeTwoLists(myLinkedList.head,myLinkedList2.head);
        myLinkedList2.show2(ret);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

11. 两个链表：找出两个链表的公共节点

找出两个链表的公共节点.
题目描述： 输入两个链表，找出它们的第一个公共结点，如果两个链表不存在相交节点，返回 null。

思路：两个链表相交，结果一定是 Y 字形的。
如下图为两个链表相交后的结果。此时 head 1 的长度为 4，head 2 的长度为 5，那我们的主体思路就是让长一点的链表先走他们的差的绝对值步，然后两个链表一起走，当两个节点第一次相遇的时候，该节点就是所求的。

/**
     * 找到两个单链表相交的起始节点
     * @param headA
     * @param headB
     * @return
     */
    public static Node getIntersectionNode(Node headA, Node headB) {
        //0.判断是否为空
        if (headA == null || headB == null) return null;
        //1.分别求出两个链表的长度
        int lenA = 0;
        int lenB = 0;
        Node pl = headA;//这两行默认headA长，headB短。
        Node ps = headB;
        while (pl != null) {
            lenA++;
            pl = pl.next;
        }
        while (ps != null) {
            lenB++;
            ps = ps.next;
        }
        pl = headA;//一定要重写回来
        ps = headB;
        int len = lenA - lenB;
        if (len < 0) {
            pl = headB;
            ps = headA;
            len = Math.abs(lenA-lenB);//这里引用了绝对值函数，相当于len = headB-headA  为确保len为正数
        }
        //pl一定是长的链表，ps一定是短的链表
        while (len != 0) {//链表长度较长的先走长度的差值
            pl = pl.next;
            len--;
        }//到此为止，两个链表就在同一个起跑线上了
        while (pl != ps) {//接下来这两个链表开始同步走
            pl = pl.next;
            ps = ps.next;
        }
        if (pl == null  ||  ps == null) {
            return null;
        }
        return pl;
    }

    /**
     * 找到两个单链表相交的起始节点
     * @param args
     */
    public static void main17(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addLast(1);
        myLinkedList.addLast(5);
        myLinkedList.addLast(7);
        myLinkedList.show();

        MyLinkedList myLinkedList2 = new MyLinkedList();
        myLinkedList2.addLast(2);
        myLinkedList2.addLast(3);
        myLinkedList2.addLast(4);
        myLinkedList2.addLast(6);
        myLinkedList2.addLast(7);
        myLinkedList2.addLast(8);
        myLinkedList2.addLast(13);
        myLinkedList2.show();

        Node ret = getIntersectionNode(myLinkedList.head, myLinkedList2.head);
        creatCut(myLinkedList.head,myLinkedList2.head);
        System.out.println(getIntersectionNode(myLinkedList.head,myLinkedList2.head).val);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

12. 其它链表题目

牛客网：链表题目.
力扣：链表题目.

总结

链表的部分的内容很复杂，需要多练多画图，遇到一个问题，首先把链表的结构图画出来，然后分析，写出大概的代码，如果一般的情况能够通过，那就得多考虑特殊位置，这样一步步的完善代码，如果没有丰富的锻炼，想一次性写完整一个链表的代码，几乎是不可能的，所以一定要多练、多画图；多练、多画图；多练、多画图！！！