• 一篇文章入门单链表+刷题实践【java实现+详细注释】

    文章目录

    节点定义

    关于节点里面所存储的信息，需要什么就添加什么，但是next字段是必须的，因为用来串联一个节点和下一个节点。

    package com.dam.data_structure.linked_list;

public class HeroNode {

    /**
     * 这三个字段自己定义
     */
    public int id;
    public String name;
    public String nickname;
    /**
     * 必要字段
     */
    public HeroNode next;

    public HeroNode(int id, String name, String nickname) {
        this.id = id;
        this.name = name;
        this.nickname = nickname;
    }

    @Override
    public String toString() {
        return "HeroNode [id=" + id + ", name=" + name + ", nickname=" + nickname + "]";
    }

    public HeroNode next(int id, String name, String nickname) {
        next = new HeroNode(id, name, nickname);
        return 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
    • 31
    • 32
    • 33

    常规添加节点方法，这样很多小伙伴可能会觉得比较麻烦

    HeroSingleLinkedList linkedList = new HeroSingleLinkedList();
 HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
        HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
        linkedList.add(hero1);
        linkedList.add(hero4);
        linkedList.add(hero2);
        linkedList.add(hero3);

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    这里提供一个快速添加节点的方法

     public HeroNode next(int id, String name, String nickname) {
     next = new HeroNode(id, name, nickname);
     return next;
 }

    • 1
    • 2
    • 3
    • 4

    使用方式

    HeroSingleLinkedList linkedList = new HeroSingleLinkedList();
        链式添加元素
        linkedList.head.next(5, "小明", "小明")
                .next(6, "小花", "小花")
                .next(7, "小华", "小华")
                .next(8, "李华", "李华");

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    链表类

    本文的链表会使用一个空的结点来作为head，该节点上面没有什么实际数据，只是为了让链表的其他方法更加容易实现

    public class HeroSingleLinkedList {
    /**
     * 先初始化一个头节点, 头节点不要动, 不存放具体的数据
     */
    private HeroNode head = new HeroNode(0, "", "");
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    获取链表长度

    注意，计算长度是从head的下一个节点开始计算

        /**
     * 获取链表长度
     *
     * @return
     */
    public int size() {
        int size = 0;
        HeroNode temp = this.head.next;
        while (temp != null) {
            size++;
            temp = temp.next;
        }
        return size;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    清空链表

    直接重置头节点就行

      /**
     * 清空链表
     */
    public void clear() {
        this.head.next = null;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    添加节点到链表尾部

    找到链表的最后一个节点，将最后一个节点的next指向要添加的节点即可

      /**
     * 添加元素
     *
     * @param heroNode
     */
    public void add(HeroNode heroNode) {
        HeroNode temp = this.head;
        找到最后一个元素，将heroNode添加即可，最后一个元素的next肯定为null
        while (temp != null) {
            if (temp.next == null) {
                //--if--找到了最后一个元素 添加元素之后即可退出
                temp.next = heroNode;
                break;
            } else {
                //--if--不是最后一个元素，继续往下面寻找
                temp = temp.next;
            }
        }
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    根据id来删除节点

    删除节点一般是遍历到要删除节点的前一个元素，然后将前一个元素的next指向null或者要删除元素的下一个节点

       /**
     * 根据id来删除节点
     *
     * @param id
     */
    public HeroNode deleteById(int id) {
        HeroNode temp = this.head;
        while (temp != null && temp.next != null) {
            if (temp.next.id == id) {
                //记录要删除的元素
                HeroNode record = temp.next;
                if (temp.next.next != null) {
                    //--if--如果还有下下个节点
                    temp.next = temp.next.next;
                } else {
                    //--if--如果没有下下节点，直接赋值为空就行
                    temp.next = null;
                }
                return record;
            }
            temp = temp.next;
        }
        System.out.println("没有找到相应id的元素，无需删除");
        return null;
    }

    • 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

    根据id来查询节点

       /**
     * 根据id来查询节点
     *
     * @param id
     */
    public HeroNode getById(int id) {
        HeroNode temp = this.head;
        while (temp != null) {
            if (temp.id == id) {
                return temp;
            }
            temp = temp.next;
        }
        System.out.println("没有找到相应id的元素");
        return null;
    }


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    修改相同id的节点信息

        /**
     * 根据id匹配来修改节点
     *
     * @param heroNode
     */
    public void update(HeroNode heroNode) {
        HeroNode temp = this.head;
        while (temp != null) {
            if (temp.id == heroNode.id) {
                temp.name = heroNode.name;
                temp.nickname = heroNode.nickname;
                return;
            }
            temp = temp.next;
        }
        System.out.println("没有找到相应id的元素，无法修改");
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    打印链表

       /**
     * 打印链表的元素
     */
    public void print() {
        //不打印头节点，从头节点的后一个元素开始
        HeroNode temp = this.head.next;
        while (temp != null) {
            System.out.println(temp.toString());
            temp = temp.next;
        }
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    逆序打印

    利用栈先进后出特性来协助

      /**
     * 逆序打印
     */
    public void reversePrint() {
        //先将所有元素存储到栈中
        Stack<HeroNode> stack = new Stack<>();
        HeroNode temp = this.head.next;
        while (temp != null) {
            stack.push(temp);
            temp = temp.next;
        }

        //从栈中取出元素并打印
        while (!stack.isEmpty()) {
            System.out.println(stack.pop().toString());
        }
    }


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    反转链表

    反转链表原理
    在这里插入图片描述

     /**
     * 原地反转链表
     *
     * @param linkedList
     */
    public static void reverseList(HeroSingleLinkedList linkedList) {
        HeroNode head = linkedList.head;

        //如果只有一个元素或者没有元素，直接退出即可
        if (head == null || head.next == null) {
            return;
        }

        HeroNode cur = head.next;
        HeroNode last = null;
        while (cur != null) {
            HeroNode temp = cur.next;
            cur.next = last;
            last = cur;
            cur = temp;
        }

        head.next = last;
    }


    • 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

    获取链表首元素

    /**
     * 获取链表的第一个元素
     *
     * @return
     */
    public HeroNode getFirst() {
        return this.head.next;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    获取链表尾元素

      /**
     * 获取链表的最后一个元素
     *
     * @return
     */
    public HeroNode getLast() {
        HeroNode temp = this.head.next;
        if (temp == null) {
            //链表为空
            return null;
        }
        while (temp.next != null) {
            temp = temp.next;
        }

        return temp;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    删除链表首元素

        /**
     * 移除链表的第一个元素
     *
     * @return
     */
    public HeroNode removeFirst() {
        HeroNode first = this.head.next;
        if (first == null) {
            System.out.println("链表中没有元素");
        } else {
            if (first.next != null) {
                this.head.next = first.next;
            } else {
                this.head.next = null;
            }
        }
        return first;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    删除链表尾元素

        /**
     * 移除链表的第一个元素
     *
     * @return
     */
    public HeroNode removeLast() {
        HeroNode temp = this.head;
        while (temp != null && temp.next != null) {
            if (temp.next.next == null) {
                //记录要删除的元素
                HeroNode record = temp.next;
                temp.next = null;
                return record;
            }
            temp = temp.next;
        }
        System.out.println("没有删除任何元素");
        return null;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    测试

    代码

    package com.dam.data_structure.linked_list.single;

import java.util.Stack;

public class HeroSingleLinkedList {
    /**
     * 先初始化一个头节点, 头节点不要动, 不存放具体的数据
     */
    private HeroNode head = new HeroNode(0, "", "");

    /**
     * 添加元素
     *
     * @param heroNode
     */
    public void add(HeroNode heroNode) {
        HeroNode temp = this.head;
        找到最后一个元素，将heroNode添加即可，最后一个元素的next肯定为null
        while (temp != null) {
            if (temp.next == null) {
                //--if--找到了最后一个元素 添加元素之后即可退出
                temp.next = heroNode;
                break;
            } else {
                //--if--不是最后一个元素，继续往下面寻找
                temp = temp.next;
            }
        }
    }

    /**
     * 根据id来删除节点
     *
     * @param id
     */
    public HeroNode deleteById(int id) {
        HeroNode temp = this.head;
        while (temp != null && temp.next != null) {
            if (temp.next.id == id) {
                //记录要删除的元素
                HeroNode record = temp.next;
                if (temp.next.next != null) {
                    //--if--如果还有下下个节点
                    temp.next = temp.next.next;
                } else {
                    //--if--如果没有下下节点，直接赋值为空就行
                    temp.next = null;
                }
                return record;
            }
            temp = temp.next;
        }
        System.out.println("没有找到相应id的元素，无需删除");
        return null;
    }

    /**
     * 根据id来查询节点
     *
     * @param id
     */
    public HeroNode getById(int id) {
        HeroNode temp = this.head;
        while (temp != null) {
            if (temp.id == id) {
                return temp;
            }
            temp = temp.next;
        }
        System.out.println("没有找到相应id的元素");
        return null;
    }

    /**
     * 根据id匹配来修改节点
     *
     * @param heroNode
     */
    public void update(HeroNode heroNode) {
        HeroNode temp = this.head;
        while (temp != null) {
            if (temp.id == heroNode.id) {
                temp.name = heroNode.name;
                temp.nickname = heroNode.nickname;
                return;
            }
            temp = temp.next;
        }
        System.out.println("没有找到相应id的元素，无法修改");
    }

    /**
     * 获取链表长度
     *
     * @return
     */
    public int size() {
        int size = 0;
        HeroNode temp = this.head.next;
        while (temp != null) {
            size++;
            temp = temp.next;
        }
        return size;
    }

    /**
     * 获取链表的第一个元素
     *
     * @return
     */
    public HeroNode getFirst() {
        return this.head.next;
    }

    /**
     * 移除链表的第一个元素
     *
     * @return
     */
    public HeroNode removeFirst() {
        HeroNode first = this.head.next;
        if (first == null) {
            System.out.println("链表中没有元素");
        } else {
            if (first.next != null) {
                this.head.next = first.next;
            } else {
                this.head.next = null;
            }
        }
        return first;
    }

    /**
     * 获取链表的最后一个元素
     *
     * @return
     */
    public HeroNode getLast() {
        HeroNode temp = this.head.next;
        if (temp == null) {
            //链表为空
            return null;
        }
        while (temp.next != null) {
            temp = temp.next;
        }

        return temp;
    }

    /**
     * 移除链表的第一个元素
     *
     * @return
     */
    public HeroNode removeLast() {
        HeroNode temp = this.head;
        while (temp != null && temp.next != null) {
            if (temp.next.next == null) {
                //记录要删除的元素
                HeroNode record = temp.next;
                temp.next = null;
                return record;
            }
            temp = temp.next;
        }
        System.out.println("没有删除任何元素");
        return null;
    }

    /**
     * 清空链表
     */
    public void clear() {
        this.head.next = null;
    }

    /**
     * 打印链表的元素
     */
    public void print() {
        //不打印头节点，从头节点的后一个元素开始
        HeroNode temp = this.head.next;
        while (temp != null) {
            System.out.println(temp.toString());
            temp = temp.next;
        }
    }

    /**
     * 逆序打印
     */
    public void reversePrint() {
        //先将所有元素存储到栈中
        Stack<HeroNode> stack = new Stack<>();
        HeroNode temp = this.head.next;
        while (temp != null) {
            stack.push(temp);
            temp = temp.next;
        }

        //从栈中取出元素并打印
        while (!stack.isEmpty()) {
            System.out.println(stack.pop().toString());
        }
    }

    /**
     * 原地反转链表
     *
     * @param linkedList
     */
    public static void reverseList(HeroSingleLinkedList linkedList) {
        HeroNode head = linkedList.head;

        //如果只有一个元素或者没有元素，直接退出即可
        if (head == null || head.next == null) {
            return;
        }

        HeroNode cur = head.next;
        HeroNode last = null;
        while (cur != null) {
            HeroNode temp = cur.next;
            cur.next = last;
            last = cur;
            cur = temp;
        }

        head.next = last;
    }

    public static void main(String[] args) {
        HeroSingleLinkedList linkedList = new HeroSingleLinkedList();

        链式添加元素
        linkedList.head.next(5, "小明", "小明")
                .next(6, "小花", "小花")
                .next(7, "小华", "小华")
                .next(8, "李华", "李华");

        插入测试
        HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
        HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
        linkedList.add(hero1);
        linkedList.add(hero4);
        linkedList.add(hero2);
        linkedList.add(hero3);

        正序打印测试
        System.out.println("正序打印测试---------------------------------------------------------------------------------------");
        linkedList.print();
        System.out.println();

        获取链表首元素
        System.out.println("获取链表首元素测试---------------------------------------------------------------------------------------");
        HeroNode first = linkedList.getFirst();
        System.out.println("first:" + first);
        System.out.println();

        移除链表的首元素
        System.out.println("移除链表的首元素---------------------------------------------------------------------------------------");
        linkedList.removeFirst();
        linkedList.print();
        System.out.println();

        获取最后一个元素
        System.out.println("获取链表最后一个元素测试---------------------------------------------------------------------------------------");
        HeroNode last = linkedList.getLast();
        System.out.println("last:" + last);
        System.out.println();

        移除链表的最后一个元素
        System.out.println("移除链表的最后一个元素---------------------------------------------------------------------------------------");
        linkedList.removeLast();
        linkedList.print();
        System.out.println();

        逆序打印测试
        System.out.println("逆序打印测试---------------------------------------------------------------------------------------");
        linkedList.reversePrint();
        System.out.println();

        获取链表长度测试
        System.out.println("获取链表长度测试---------------------------------------------------------------------------------------");
        System.out.println("链表长度：" + linkedList.size());
        System.out.println();

        反转链表
        System.out.println("反转链表测试---------------------------------------------------------------------------------------");
        HeroSingleLinkedList.reverseList(linkedList);
        linkedList.print();
        System.out.println();

        修改元素
        System.out.println("修改链表元素测试---------------------------------------------------------------------------------------");
        linkedList.update(new HeroNode(4, "武松", "行者"));
        linkedList.print();
        System.out.println();

        根据id查询元素
        System.out.println("根据id查询元素---------------------------------------------------------------------------------------");
        System.out.println("linkedList.getById(2):" + linkedList.getById(2));
        System.out.println();

        删除元素
        linkedList.clear();
        ///链式添加元素
        linkedList.head.next(5, "小明", "小明")
                .next(6, "小花", "小花")
                .next(7, "小华", "小华")
                .next(8, "李华", "李华")
                .next(1, "宋江", "及时雨")
                .next(2, "卢俊义", "玉麒")
                .next(3, "吴用", "智多星")
                .next(4, "林冲", "豹子头");
        System.out.println("删除链表元素测试---------------------------------------------------------------------------------------");
        linkedList.print();
        System.out.println("删除10");
        linkedList.deleteById(10);
        System.out.println("删除1");
        linkedList.deleteById(1);
        linkedList.print();
        System.out.println("删除3");
        linkedList.deleteById(3);
        linkedList.print();
        System.out.println("删除4");
        linkedList.deleteById(4);
        linkedList.print();
        System.out.println("删除2");
        linkedList.deleteById(2);
        linkedList.print();
        System.out.println();
        System.out.println("删除6");
        linkedList.deleteById(6);
        linkedList.print();
        System.out.println();
        System.out.println("删除尾元素");
        linkedList.removeLast();
        linkedList.print();
        System.out.println();
        System.out.println("删除尾元素");
        linkedList.removeLast();
        linkedList.print();
        System.out.println();
        System.out.println("删除尾元素");
        linkedList.removeLast();
        linkedList.print();
        System.out.println();
        System.out.println("删除尾元素");
        linkedList.removeLast();
        linkedList.print();
        System.out.println();
    }
}


    • 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
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178
    • 179
    • 180
    • 181
    • 182
    • 183
    • 184
    • 185
    • 186
    • 187
    • 188
    • 189
    • 190
    • 191
    • 192
    • 193
    • 194
    • 195
    • 196
    • 197
    • 198
    • 199
    • 200
    • 201
    • 202
    • 203
    • 204
    • 205
    • 206
    • 207
    • 208
    • 209
    • 210
    • 211
    • 212
    • 213
    • 214
    • 215
    • 216
    • 217
    • 218
    • 219
    • 220
    • 221
    • 222
    • 223
    • 224
    • 225
    • 226
    • 227
    • 228
    • 229
    • 230
    • 231
    • 232
    • 233
    • 234
    • 235
    • 236
    • 237
    • 238
    • 239
    • 240
    • 241
    • 242
    • 243
    • 244
    • 245
    • 246
    • 247
    • 248
    • 249
    • 250
    • 251
    • 252
    • 253
    • 254
    • 255
    • 256
    • 257
    • 258
    • 259
    • 260
    • 261
    • 262
    • 263
    • 264
    • 265
    • 266
    • 267
    • 268
    • 269
    • 270
    • 271
    • 272
    • 273
    • 274
    • 275
    • 276
    • 277
    • 278
    • 279
    • 280
    • 281
    • 282
    • 283
    • 284
    • 285
    • 286
    • 287
    • 288
    • 289
    • 290
    • 291
    • 292
    • 293
    • 294
    • 295
    • 296
    • 297
    • 298
    • 299
    • 300
    • 301
    • 302
    • 303
    • 304
    • 305
    • 306
    • 307
    • 308
    • 309
    • 310
    • 311
    • 312
    • 313
    • 314
    • 315
    • 316
    • 317
    • 318
    • 319
    • 320
    • 321
    • 322
    • 323
    • 324
    • 325
    • 326
    • 327
    • 328
    • 329
    • 330
    • 331
    • 332
    • 333
    • 334
    • 335
    • 336
    • 337
    • 338
    • 339
    • 340
    • 341
    • 342
    • 343
    • 344
    • 345
    • 346
    • 347
    • 348
    • 349
    • 350
    • 351
    • 352
    • 353
    • 354
    • 355
    • 356
    • 357
    • 358
    • 359
    • 360

    打印信息

    E:\Development\Java\JDK\jdk8\jdk\bin\java.exe "-javaagent:E:\Development\IDE\IDEA\IntelliJ IDEA 2020.1\lib\idea_rt.jar=1671:E:\Development\IDE\IDEA\IntelliJ IDEA 2020.1\bin" -Dfile.encoding=UTF-8 -classpath E:\Development\Java\JDK\jdk8\jdk\jre\lib\charsets.jar;E:\Development\Java\JDK\jdk8\jdk\jre\lib\deploy.jar;E:\Development\Java\JDK\jdk8\jdk\jre\lib\ext\access-bridge-64.jar;E:\Development\Java\JDK\jdk8\jdk\jre\lib\ext\cldrdata.jar;E:\Development\Java\JDK\jdk8\jdk\jre\lib\ext\dnsns.jar;E:\Development\Java\JDK\jdk8\jdk\jre\lib\ext\jaccess.jar;E:\Development\Java\JDK\jdk8\jdk\jre\lib\ext\jfxrt.jar;E:\Development\Java\JDK\jdk8\jdk\jre\lib\ext\localedata.jar;E:\Development\Java\JDK\jdk8\jdk\jre\lib\ext\nashorn.jar;E:\Development\Java\JDK\jdk8\jdk\jre\lib\ext\sunec.jar;E:\Development\Java\JDK\jdk8\jdk\jre\lib\ext\sunjce_provider.jar;E:\Development\Java\JDK\jdk8\jdk\jre\lib\ext\sunmscapi.jar;E:\Development\Java\JDK\jdk8\jdk\jre\lib\ext\sunpkcs11.jar;E:\Development\Java\JDK\jdk8\jdk\jre\lib\ext\zipfs.jar;E:\Development\Java\JDK\jdk8\jdk\jre\lib\javaws.jar;E:\Development\Java\JDK\jdk8\jdk\jre\lib\jce.jar;E:\Development\Java\JDK\jdk8\jdk\jre\lib\jfr.jar;E:\Development\Java\JDK\jdk8\jdk\jre\lib\jfxswt.jar;E:\Development\Java\JDK\jdk8\jdk\jre\lib\jsse.jar;E:\Development\Java\JDK\jdk8\jdk\jre\lib\management-agent.jar;E:\Development\Java\JDK\jdk8\jdk\jre\lib\plugin.jar;E:\Development\Java\JDK\jdk8\jdk\jre\lib\resources.jar;E:\Development\Java\JDK\jdk8\jdk\jre\lib\rt.jar;E:\Projects\damFile\AlgorithmPractice\target\classes;E:\Development\Java\Cplex\install\cplex\lib\cplex.jar;E:\Development\Java\Maven\repository\junit\junit\4.13\junit-4.13.jar;E:\Development\Java\Maven\repository\org\hamcrest\hamcrest-core\1.3\hamcrest-core-1.3.jar;E:\Development\Java\Maven\repository\org\projectlombok\lombok\1.18.22\lombok-1.18.22.jar;E:\Development\Java\Maven\repository\com\alibaba\fastjson\1.2.62\fastjson-1.2.62.jar;E:\Development\Java\Maven\repository\org\apache\poi\poi\3.9\poi-3.9.jar;E:\Development\Java\Maven\repository\commons-codec\commons-codec\1.5\commons-codec-1.5.jar;E:\Development\Java\Maven\repository\org\apache\poi\poi-ooxml\3.9\poi-ooxml-3.9.jar;E:\Development\Java\Maven\repository\dom4j\dom4j\1.6.1\dom4j-1.6.1.jar;E:\Development\Java\Maven\repository\xml-apis\xml-apis\1.0.b2\xml-apis-1.0.b2.jar;E:\Development\Java\Maven\repository\org\apache\poi\poi-ooxml-schemas\3.9\poi-ooxml-schemas-3.9.jar;E:\Development\Java\Maven\repository\org\apache\xmlbeans\xmlbeans\2.3.0\xmlbeans-2.3.0.jar;E:\Development\Java\Maven\repository\stax\stax-api\1.0.1\stax-api-1.0.1.jar com.dam.data_structure.linked_list.single.HeroSingleLinkedList
正序打印测试---------------------------------------------------------------------------------------
HeroNode [id=5, name=小明, nickname=小明]
HeroNode [id=6, name=小花, nickname=小花]
HeroNode [id=7, name=小华, nickname=小华]
HeroNode [id=8, name=李华, nickname=李华]
HeroNode [id=1, name=宋江, nickname=及时雨]
HeroNode [id=4, name=林冲, nickname=豹子头]
HeroNode [id=2, name=卢俊义, nickname=玉麒麟]
HeroNode [id=3, name=吴用, nickname=智多星]

获取链表首元素测试---------------------------------------------------------------------------------------
first:HeroNode [id=5, name=小明, nickname=小明]

移除链表的首元素---------------------------------------------------------------------------------------
HeroNode [id=6, name=小花, nickname=小花]
HeroNode [id=7, name=小华, nickname=小华]
HeroNode [id=8, name=李华, nickname=李华]
HeroNode [id=1, name=宋江, nickname=及时雨]
HeroNode [id=4, name=林冲, nickname=豹子头]
HeroNode [id=2, name=卢俊义, nickname=玉麒麟]
HeroNode [id=3, name=吴用, nickname=智多星]

获取链表最后一个元素测试---------------------------------------------------------------------------------------
last:HeroNode [id=3, name=吴用, nickname=智多星]

移除链表的最后一个元素---------------------------------------------------------------------------------------
HeroNode [id=6, name=小花, nickname=小花]
HeroNode [id=7, name=小华, nickname=小华]
HeroNode [id=8, name=李华, nickname=李华]
HeroNode [id=1, name=宋江, nickname=及时雨]
HeroNode [id=4, name=林冲, nickname=豹子头]
HeroNode [id=2, name=卢俊义, nickname=玉麒麟]

逆序打印测试---------------------------------------------------------------------------------------
HeroNode [id=2, name=卢俊义, nickname=玉麒麟]
HeroNode [id=4, name=林冲, nickname=豹子头]
HeroNode [id=1, name=宋江, nickname=及时雨]
HeroNode [id=8, name=李华, nickname=李华]
HeroNode [id=7, name=小华, nickname=小华]
HeroNode [id=6, name=小花, nickname=小花]

获取链表长度测试---------------------------------------------------------------------------------------
链表长度：6

反转链表测试---------------------------------------------------------------------------------------
HeroNode [id=2, name=卢俊义, nickname=玉麒麟]
HeroNode [id=4, name=林冲, nickname=豹子头]
HeroNode [id=1, name=宋江, nickname=及时雨]
HeroNode [id=8, name=李华, nickname=李华]
HeroNode [id=7, name=小华, nickname=小华]
HeroNode [id=6, name=小花, nickname=小花]

修改链表元素测试---------------------------------------------------------------------------------------
HeroNode [id=2, name=卢俊义, nickname=玉麒麟]
HeroNode [id=4, name=武松, nickname=行者]
HeroNode [id=1, name=宋江, nickname=及时雨]
HeroNode [id=8, name=李华, nickname=李华]
HeroNode [id=7, name=小华, nickname=小华]
HeroNode [id=6, name=小花, nickname=小花]

根据id查询元素---------------------------------------------------------------------------------------
linkedList.getById(2):HeroNode [id=2, name=卢俊义, nickname=玉麒麟]

删除链表元素测试---------------------------------------------------------------------------------------
HeroNode [id=5, name=小明, nickname=小明]
HeroNode [id=6, name=小花, nickname=小花]
HeroNode [id=7, name=小华, nickname=小华]
HeroNode [id=8, name=李华, nickname=李华]
HeroNode [id=1, name=宋江, nickname=及时雨]
HeroNode [id=2, name=卢俊义, nickname=玉麒]
HeroNode [id=3, name=吴用, nickname=智多星]
HeroNode [id=4, name=林冲, nickname=豹子头]
删除10
没有找到相应id的元素，无需删除
删除1
HeroNode [id=5, name=小明, nickname=小明]
HeroNode [id=6, name=小花, nickname=小花]
HeroNode [id=7, name=小华, nickname=小华]
HeroNode [id=8, name=李华, nickname=李华]
HeroNode [id=2, name=卢俊义, nickname=玉麒]
HeroNode [id=3, name=吴用, nickname=智多星]
HeroNode [id=4, name=林冲, nickname=豹子头]
删除3
HeroNode [id=5, name=小明, nickname=小明]
HeroNode [id=6, name=小花, nickname=小花]
HeroNode [id=7, name=小华, nickname=小华]
HeroNode [id=8, name=李华, nickname=李华]
HeroNode [id=2, name=卢俊义, nickname=玉麒]
HeroNode [id=4, name=林冲, nickname=豹子头]
删除4
HeroNode [id=5, name=小明, nickname=小明]
HeroNode [id=6, name=小花, nickname=小花]
HeroNode [id=7, name=小华, nickname=小华]
HeroNode [id=8, name=李华, nickname=李华]
HeroNode [id=2, name=卢俊义, nickname=玉麒]
删除2
HeroNode [id=5, name=小明, nickname=小明]
HeroNode [id=6, name=小花, nickname=小花]
HeroNode [id=7, name=小华, nickname=小华]
HeroNode [id=8, name=李华, nickname=李华]

删除6
HeroNode [id=5, name=小明, nickname=小明]
HeroNode [id=7, name=小华, nickname=小华]
HeroNode [id=8, name=李华, nickname=李华]

删除尾元素
HeroNode [id=5, name=小明, nickname=小明]
HeroNode [id=7, name=小华, nickname=小华]

删除尾元素
HeroNode [id=5, name=小明, nickname=小明]

删除尾元素

删除尾元素
没有删除任何元素


Process finished with exit code 0


    • 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
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122

    习题

    反转链表

    https://leetcode.cn/problems/fan-zhuan-lian-biao-lcof/

    /**
 * 注意：head上面也有值，不是单纯作为头节点
 * @param head
 * @return
 */
public ListNode reverseList(ListNode head) {
    ListNode cur = head;
    ListNode last = null;
    while (cur != null) {
        //先将cur后面的部分存储起来
        ListNode temp = cur.next;
        cur.next = last;
        last = cur;
        cur = temp;
    }
    return last;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    删除链表的节点

    https://leetcode.cn/problems/shan-chu-lian-biao-de-jie-dian-lcof/

    public ListNode deleteNode(ListNode head, int val) {
    if (head == null) {
        return null;
    }
    if (head.val == val) {
    	//删除头节点，直接返回头节点的下一个节点即可
        return head.next;
    }
    ListNode temp = head;
    while (temp != null && temp.next != null) {
        if (temp.next.val == val) {
            if (temp.next.next != null) {
                temp.next = temp.next.next;
            } else {
                temp.next = null;
            }
            break;
        }
        temp = temp.next;
    }
    return head;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    删除链表的倒数第k个节点

    https://leetcode.cn/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/

    public ListNode getKthFromEnd(ListNode head, int k) {
    ListNode fast = head;
    ListNode slow = head;
    //让快指针先走k步
    for (int i = 0; i < k; i++) {
        fast = fast.next;
    }
    //快慢一起走，快走到尽头，慢就是倒数第k个
    while (true) {
        if (fast == null) {
            break;
        }
        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

    合并两个排序的链表

    https://leetcode.cn/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/description/

        /**
     * 借助辅助节点
     *
     * @param l1
     * @param l2
     * @return
     */
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        //添加一个辅助节点，主要是方便后面的连接操作
        ListNode merge = new ListNode(-1);
        ListNode temp = merge;
        
        //当l1和l2都不为空的时候，就需要判断哪个更小
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                temp.next = l1;
                l1 = l1.next;
            } else {
                temp.next = l2;
                l2 = l2.next;
            }
            temp = temp.next;
        }
        //当有一个为空之后，后面的值直接和不为空的那个链表片段一样就行
        temp.next = l1 != null ? l1 : l2;

        //注意返回的是辅助节点.next
        return merge.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
  • 相关阅读:
    项目管理过程组
    Sql Server SQL查询优化方法
    计网 | 一文解析TCP协议所有知识点
    【英雄哥六月集训】第 22天: 有序集合
    基于SSM+SpringBoot+MySQL+Vue前后端分离的高校考试管理系统
    算法通过村第十一关-位运算|青铜笔记|初始位运算
    力扣第38天----第139题
    【深入浅出Spring原理及实战】「缓存Cache开发系列」带你深入分析Spring所提供的缓存Cache抽象详解的核心原理探索
    【C++ Miscellany】C++重要的几项改变、标准程序库
    python 图像相减的不同方法
  • 原文地址：https://blog.csdn.net/laodanqiu/article/details/127925284