• 链表

    章节目录：

    一、链表

    1.1 概述

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

    • 链表由一系列结点组成（链表中每一个元素称为结点），结点可以在运行时动态生成。

    • 每个结点包括两个部分：一个是存储数据元素的数据域（data域），另一个是存储下一个结点地址的指针域（next域）。

    • 链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定。

    • 示意图：

    在这里插入图片描述

    二、单向链表

    2.1 实现思路

    需求：使用带头节点的单向链表，完成对学生对象的增删改查操作。

    • 添加方式一（链尾添加）：

    在这里插入图片描述

    • 添加方式二（根据顺序（指定位置）添加）：

    在这里插入图片描述

    • 修改节点：遍历并通过数据域信息进行判断，找到该节点后完成相应的修改操作。
    • 删除节点：

    在这里插入图片描述

    2.2 代码示例

    需求：实现单向链表的增（顺序链尾添加、指定位置添加）删改查、找到单链表倒数第几的节点、获取当前链表大小（即有效数据个数）、链表反转（改变链表结构）、反向打印（不破坏链表结构）、合并两个链表并排序。

    public class SingleLinkedListDemo {

    public static void main(String[] args) {
        SingleLinkedList singleLinkedList = new SingleLinkedList();

        System.out.println("---[顺序添加]结果如下:---");
        singleLinkedList.add(new Student(1, "张三"));
        singleLinkedList.add(new Student(2, "李四"));
        singleLinkedList.add(new Student(4, "田七"));
        SingleLinkedList.foreach(singleLinkedList.getHead());
        // ---[顺序添加]结果如下:---
        // no=1, name=张三
        // no=2, name=李四
        // no=4, name=田七

        System.out.println();
        System.out.println("---[指定位置添加]结果如下:---");
        singleLinkedList.addByOrder(new Student(3, "(赵六)"));
        SingleLinkedList.foreach(singleLinkedList.getHead());
        // ---[指定位置添加]结果如下:---
        // no=1, name=张三
        // no=2, name=李四
        // no=3, name=(赵六)
        // no=4, name=田七

        System.out.println();
        System.out.println("---[链表反转]结果如下:---");
        SingleLinkedList.reverse(singleLinkedList.getHead());
        SingleLinkedList.foreach(singleLinkedList.getHead());
        // ---[链表反转]结果如下:---
        // no=4, name=田七
        // no=3, name=(赵六)
        // no=2, name=李四
        // no=1, name=张三

        System.out.println();
        System.out.println("---[链表反向打印]结果如下:---");
        SingleLinkedList.reversePrint(singleLinkedList.getHead());
        // ---[链表反向打印]结果如下:---
        // no=1, name=张三
        // no=2, name=李四
        // no=3, name=(赵六)
        // no=4, name=田七

        System.out.println();
        System.out.println("---[修改节点]结果如下:---");
        singleLinkedList.update(new Student(3, "(王九)"));
        SingleLinkedList.foreach(singleLinkedList.getHead());
        // ---[修改节点]结果如下:---
        // no=4, name=田七
        // no=3, name=(王九)
        // no=2, name=李四
        // no=1, name=张三

        System.out.println();
        System.out.println("---[删除节点]结果如下:---");
        singleLinkedList.delete(3);
        SingleLinkedList.foreach(singleLinkedList.getHead());
        // ---[删除节点]结果如下:---
        // no=4, name=田七
        // no=2, name=李四
        // no=1, name=张三

        System.out.println();
        System.out.println("---获取[当前链表中有效数据的个数]结果如下:---");
        System.out.println(SingleLinkedList.size(singleLinkedList.getHead()));
        // ---获取[当前链表中有效数据的个数]结果如下:---
        // 3

        System.out.println();
        System.out.println("---获取[当前链表中倒数第二个数据]结果如下:---");
        Student reciprocalNode = SingleLinkedList.findReciprocalNode(
                singleLinkedList.getHead(), 2);
        System.out.println(reciprocalNode);
        // ---获取[当前链表中倒数第二个数据]结果如下:---
        // no=2, name=李四
    }

    /**
     * 测试两个链表合并后排序。
     */
    @Test
    public void testMerge() {
        SingleLinkedList s1 = new SingleLinkedList();
        s1.add(new Student(1, "a"));
        s1.add(new Student(3, "c"));
        s1.add(new Student(5, "e"));

        SingleLinkedList s2 = new SingleLinkedList();
        s2.add(new Student(2, "b"));
        s2.add(new Student(4, "d"));

        Student mergeHead = SingleLinkedList.mergeAndSorted(s1.getHead(), s2.getHead());
        assert mergeHead != null;
        System.out.println("---[链表合并排序后]结果如下:---");
        SingleLinkedList.foreach(mergeHead);
        // ---[链表合并排序后]结果如下:---
        // no=1, name=a
        // no=2, name=b
        // no=3, name=c
        // no=4, name=d
        // no=5, name=e
    }
}

/**
 * 学生节点。
 */
class Student {
    public int no;
    public String name;

    /**
     * 指向后一节点。
     */
    public Student next;

    public Student(int no, String name) {
        this.no = no;
        this.name = name;
    }

    @Override
    public String toString() {
        return "no=" + no +
                ", name=" + name;
    }
}

/**
 * 单向链表实现。
 */
class SingleLinkedList {

    /**
     * 头节点（勿动，仅占位）。
     */
    private final Student head = new Student(0, "");

    public Student getHead() {
        return head;
    }

    /**
     * 断言链表是否为空。
     *
     * @param node 节点
     */
    private static void assertLinkedListIsNull(Student node) {
        if (null == node || null == node.next) {
            throw new NullPointerException("链表为空!");
        }
    }

    /**
     * 迭代器。
     *
     * @param head 头节点
     */
    public static void foreach(Student head) {
        assertLinkedListIsNull(head);
        // 由于头节点不能动，所以这里要添加辅助指针来帮助进行遍历。
        Student pointer = head;
        while (null != pointer.next) {
            System.out.println(pointer.next);
            // 后移。
            pointer = pointer.next;
        }
    }

    /**
     * 链尾添加。
     *
     * @param node 节点
     */
    public void add(Student node) {
        Student pointer = this.head;
        while (null != pointer.next) {
            pointer = pointer.next;
        }
        // 循环终止时，表示到了链尾。
        pointer.next = node;
    }

    /**
     * 根据编号指定位置进行添加。
     *
     * @param node 节点
     */
    public void addByOrder(Student node) {
        Student pointer = this.head;
        boolean exist = false;
        while (null != pointer.next) {
            // 1.找到了插入位置。
            if (pointer.next.no > node.no) {
                break;
                // 2.节点编号已存在。
            } else if (pointer.next.no == node.no) {
                exist = true;
                break;
            }
            // 后移。
            pointer = pointer.next;
        }

        // 判断循环终止的条件。
        if (exist) {
            System.out.printf("编号[%d]的节点已存在，添加失败!\n", node.no);
        } else {
            // 插入。
            node.next = pointer.next;
            pointer.next = node;
        }
    }

    /**
     * 更新节点。
     *
     * @param node 节点
     */
    public void update(Student node) {
        Student pointer = this.head;
        boolean found = false;
        assertLinkedListIsNull(pointer);
        while (null != pointer.next) {
            // 找到了需要修改的节点。
            if (pointer.next.no == node.no) {
                found = true;
                break;
            }
            pointer = pointer.next;
        }

        if (found) {
            pointer.next.name = node.name;
        } else {
            System.out.printf("编号[%d]的节点不存在，修改失败。\n", node.no);
        }
    }

    /**
     * 删除节点。
     *
     * @param no 编号
     */
    public void delete(int no) {
        Student pointer = this.head;
        boolean found = false;
        assertLinkedListIsNull(pointer);
        while (null != pointer.next) {
            if (pointer.next.no == no) {
                found = true;
                break;
            }
            pointer = pointer.next;
        }

        if (found) {
            // 指向下下个节点，被跳过节点将失去引用被垃圾回收机制进行回收。
            pointer.next = pointer.next.next;
        } else {
            System.out.printf("编号[%d]的节点不存在，删除失败。\n", no);
        }
    }

    /**
     * 链表大小（即有效数据个数）。
     *
     * @param head 节点
     * @return int
     */
    public static int size(Student head) {
        Student pointer = head;
        if (null == pointer.next) {
            return 0;
        }

        int size = 0;
        while (null != pointer.next) {
            size++;
            pointer = pointer.next;
        }
        return size;
    }

    /**
     * 找到倒数第几的节点。
     *
     * @param head  头节点
     * @param index 倒数第几
     * @return {@link Student}
     */
    public static Student findReciprocalNode(Student head, int index) {
        assertLinkedListIsNull(head);
        int size = size(head);
        if (0 >= index || index > size) {
            return null;
        }
        Student pointer = head;
        // 假设3个数据，需要倒数第2个，3-2=1。则循环1次。
        for (int i = 0; i < (size - index); i++) {
            pointer = pointer.next;
        }
        return pointer.next;
    }

    /**
     * 链表反转（改变链表结构）。
     *
     * @param head 头节点
     */
    public static void reverse(Student head) {
        // 链表中没有节点或者只有一个节点时，无需反转。
        if (null == head.next || null == head.next.next) {
            return;
        }
        // 辅助指针。
        Student pointer = head.next;
        // 临时变量，用于存储当前节点的下一节点。
        Student temp;
        // 新的链表头。
        Student reverseHead = new Student(0, "");
        while (null != pointer) {
            temp = pointer.next;
            // 顺序取出后进行赋值。
            pointer.next = reverseHead.next;
            reverseHead.next = pointer;
            // 后移。
            pointer = temp;
        }
        // 节点指向，完成反转。
        head.next = reverseHead.next;
    }

    /**
     * 反向打印（不破坏链表结构）。
     *
     * @param head 头
     */
    public static void reversePrint(Student head) {
        assertLinkedListIsNull(head);
        Student pointer = head.next;
        Stack<Student> stack = new Stack<>();
        // 压栈。
        while (null != pointer) {
            stack.push(pointer);
            pointer = pointer.next;
        }
        // 弹栈。
        while (!stack.isEmpty()) {
            System.out.println(stack.pop());
        }
    }

    /**
     * 合并两个链表并排序。
     *
     * @param head1 head1
     * @param head2 head2
     * @return {@link Student}
     */
    public static Student mergeAndSorted(Student head1, Student head2) {
        if (null == head1.next && null == head2.next) {
            return null;
        }
        // 较小头节点。
        Student head = head1.no <= head2.no ? head1 : head2;
        // 较小头节点的下一节点。
        Student cur1 = head.next;
        // 较大头节点。
        Student cur2 = (head == head1) ? head2 : head1;
        // 辅助指针
        Student pointer = head;
        while (null != cur1 && null != cur2) {
            // 较小值插入链表。
            if (cur1.no <= cur2.no) {
                pointer.next = cur1;
                cur1 = cur1.next;
            } else {
                pointer.next = cur2;
                cur2 = cur2.next;
            }
            // 后移。
            pointer = pointer.next;
        }
        pointer.next = (null != cur1) ? cur1 : cur2;
        return head.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
    • 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
    • 361
    • 362
    • 363
    • 364
    • 365
    • 366
    • 367
    • 368
    • 369
    • 370
    • 371
    • 372
    • 373
    • 374
    • 375
    • 376
    • 377
    • 378
    • 379
    • 380
    • 381
    • 382
    • 383
    • 384
    • 385
    • 386
    • 387
    • 388
    • 389

    三、双向链表

    3.1 实现思路

    与单向链表不同的是，双向链表增加了指向前一节点的属性。

    • 两种链表区别：

      • 单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找。

      • 单向链表不能自我删除，需要靠辅助节点 ，而双向链表，则可以自我删除。所以前面我们单链表删除

        时节点，总是需要找到 pointer 的下一个节点。

    • 双向链表增删改查实现思路分析：

      • 遍历：实现与单链表一样，只是可以向前，也可以向后查找。
      • 添加：默认添加到双向链表的最后。
      • 修改：实现与单链表一样。
      • 删除：因为是双向链表，因此，我们可以实现自我删除某个节点。

    • 示意图：

    在这里插入图片描述

    3.2 代码示例

    需求：实现双向链表的增（顺序链尾添加、指定位置添加）删改查。

    public class DoubleLinkedListDemo {
    public static void main(String[] args) {
        DoubleLinkedList doubleLinkedList = new DoubleLinkedList();

        System.out.println("---[顺序添加]结果如下:---");
        doubleLinkedList.add(new Teacher(1, "张老师"));
        doubleLinkedList.add(new Teacher(2, "李老师"));
        doubleLinkedList.add(new Teacher(4, "田老师"));
        doubleLinkedList.foreach();
        // ---[顺序添加]结果如下:---
        // no=1, name=张老师
        // no=2, name=李老师
        // no=4, name=田老师

        System.out.println();
        System.out.println("---[指定位置添加]结果如下:---");
        doubleLinkedList.addByOrder(new Teacher(3, "(赵老师)"));
        doubleLinkedList.foreach();
        // ---[指定位置添加]结果如下:---
        // DEBUG INFO (addByOrder result) : prev.no=[2] ,cur.no=[3] ,next.no=[4]
        // no=1, name=张老师
        // no=2, name=李老师
        // no=3, name=(赵老师)
        // no=4, name=田老师

        System.out.println();
        System.out.println("---[修改节点]结果如下:---");
        doubleLinkedList.update(new Teacher(3, "(王老师)"));
        doubleLinkedList.foreach();
        // ---[修改节点]结果如下:---
        // no=1, name=张老师
        // no=2, name=李老师
        // no=3, name=(王老师)
        // no=4, name=田老师

        System.out.println();
        System.out.println("---[删除节点]结果如下:---");
        doubleLinkedList.delete(3);
        doubleLinkedList.foreach();
        // ---[删除节点]结果如下:---
        // DEBUG INFO (delete before) : prev.no=[2] ,cur.no=[3] ,next.no=[4]
        // no=1, name=张老师
        // no=2, name=李老师
        // no=4, name=田老师
    }
}

/**
 * 双向链表实现。
 */
class DoubleLinkedList {

    /**
     * 头节点勿动。
     */
    private final Teacher head = new Teacher(0, "");

    public Teacher getHead() {
        return head;
    }

    /**
     * 链尾添加。
     *
     * @param node 节点
     */
    public void add(Teacher node) {
        Teacher pointer = this.head;
        while (null != pointer.next) {
            pointer = pointer.next;
        }
        pointer.next = node;
        node.prev = pointer;
    }

    /**
     * 根据编号指定位置进行添加。
     *
     * @param node 节点
     */
    public void addByOrder(Teacher node) {
        Teacher pointer = this.head;
        boolean exist = false;
        while (null != pointer.next) {
            if (pointer.next.no > node.no) {
                break;
            } else if (pointer.next.no == node.no) {
                exist = true;
                break;
            }
            pointer = pointer.next;
        }

        if (exist) {
            System.out.printf("编号[%d]的节点已存在，添加失败!\n", node.no);
        } else {
            // 后一节点双链指向。no.3 <-> no.2
            // 注意这里后一节点可能为空
            if (null != pointer.next) {
                node.next = pointer.next;
                node.next.prev = node;
            }

            // 前一节点双链指向。no.1 <-> no.2
            pointer.next = node;
            node.prev = pointer;

            // 结果验证。
            System.out.printf("DEBUG INFO (addByOrder result) : prev.no=[%d] ,cur.no=[%d] ,next.no=[%d]\n",
                    node.prev.no,
                    node.no,
                    (null == node.next ? null : node.next.no));
        }
    }

    /**
     * 更新节点。
     *
     * @param node 节点
     */
    public void update(Teacher node) {
        Teacher pointer = this.head;
        assertLinkedListIsNull(pointer);
        boolean found = false;
        while (null != pointer.next) {
            if (pointer.next.no == node.no) {
                found = true;
                break;
            }
            pointer = pointer.next;
        }

        if (found) {
            // 只是当前节点的值变了，前后链接指向关系没有动。
            pointer.next.name = node.name;
        } else {
            System.out.printf("编号[%d]的节点不存在，修改失败。\n", node.no);
        }
    }

    /**
     * 删除节点。
     *
     * @param no 编号
     */
    public void delete(int no) {
        Teacher pointer = this.head.next;
        assertLinkedListIsNull(pointer);
        boolean found = false;
        while (null != pointer) {
            if (pointer.no == no) {
                found = true;
                break;
            }
            pointer = pointer.next;
        }
        if (found) {
            // before: no.2(pointer.prev) <-> no.3(pointer) <-> no.4(pointer.next)
            // after: no.2 <-> no.4
            System.out.printf("DEBUG INFO (delete before) : prev.no=[%d] ,cur.no=[%d] ,next.no=[%d]\n",
                    pointer.prev.no,
                    pointer.no,
                    pointer.next.no);

            // 后链被删除的后一节点。
            pointer.prev.next = pointer.next;
            // 注意:如果是最后一个节点，就不需要执行下面这句话，否则出现空指针!
            if (pointer.next != null) {
                // 被删除的后一节点往前链。
                pointer.next.prev = pointer.prev;
            }
        } else {
            System.out.printf("编号[%d]的节点不存在，删除失败。\n", no);
        }
    }

    /**
     * 断言链表是否为空。
     *
     * @param node 节点
     */
    private static void assertLinkedListIsNull(Teacher node) {
        if (null == node || null == node.next) {
            throw new NullPointerException("链表为空!");
        }
    }

    /**
     * 迭代器。
     */
    public void foreach() {
        Teacher pointer = this.head;
        assertLinkedListIsNull(pointer);
        while (null != pointer.next) {
            System.out.println(pointer.next);
            pointer = pointer.next;
        }
    }
}

/**
 * 教师节点。
 */
class Teacher {

    public int no;
    public String name;

    /**
     * 指向前一节点。
     */
    public Teacher prev;

    /**
     * 指向后一节点。
     */
    public Teacher next;

    public Teacher(int no, String name) {
        this.no = no;
        this.name = name;
    }

    @Override
    public String toString() {
        return "no=" + no +
                ", name=" + name;
    }
}

    • 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

    四、单向环形链表

    4.1 约瑟夫问题

    约瑟夫问题，是一个计算机科学和数学中的问题，在计算机编程的算法中，类似问题又称为约瑟夫环，又称“丢手绢问题”。

    据说著名犹太历史学家 Josephus 有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与 Josephus 及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而 Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决。Josephus 要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

    • 问题简述：设编号为 1，2，… n 的 n 个人围坐一圈，约定编号为 k（1<=k<=n）的人从 1 开始报数，数到 m 的那个人出列，它的下一位又从 1 开始报数，数到 m 的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。

    4.2 实现思路

    • 用一个不带头结点的循环链表来处理 Josephus 问题：先构成一个有 n 个结点的单循环链表，然后由 k 结点起从 1 开始计数，计到 m 时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从 1 开始计数，直到最后一个结点从链表中删除算法结束。

    • 构建单向环形链表：

      • 先创建第一个节点，让 first 指向该节点 ，并形成环。
      • 后面每创建一个新节点，就把该节点加入到环形链表中。

    • 遍历单向环形链表：

      • 通过辅助指针，指向first节点。
      • 循环至指针指向下一轮 first节点出现为止。

    • 示意图：

    在这里插入图片描述

    4.3 代码示例

    public class Josephus {
    public static void main(String[] args) {
        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();

        System.out.println("[添加节点]结果如下:");
        circleSingleLinkedList.add(5);
        circleSingleLinkedList.foreach();
        // [添加节点]结果如下:
        // no=1
        // no=2
        // no=3
        // no=4
        // no=5

        System.out.println();
        System.out.println("[出圈]结果如下:");
        // 圈中总计节点个数5，从1开始计数，每次数两下，被点到的编号出圈。
        // 期望结果：2 -> 4 -> 1  -> 5  -> 3
        circleSingleLinkedList.count(1, 2, 5);
        // [出圈]结果如下:
        // 编号[2]出圈
        // 编号[4]出圈
        // 编号[1]出圈
        // 编号[5]出圈
        // 圈中剩余编号为[3]
    }
}

class CircleSingleLinkedList {


    /**
     * 首节点。
     */
    private Node first = null;


    /**
     * 添加节点。
     *
     * @param nums 生成的节点个数
     */
    public void add(int nums) {
        // 值校验，添加的点需要大于1。
        if (1 > nums) {
            throw new IllegalArgumentException();
        }
        // 辅助指针。
        Node pointer = null;
        for (int i = 1; i <= nums; i++) {
            Node node = new Node(i, null);
            if (1 == i) {
                // 构造环（首尾相连）。
                first = node;
                first.setNext(first);
                // 并指向第一个节点。
                pointer = first;
            } else {
                // 节点往后添加。
                if (null != pointer) {
                    pointer.setNext(node);
                    // 闭环。
                    node.setNext(first);
                    pointer = node;
                }
            }
        }
    }


    /**
     * 迭代器。
     */
    public void foreach() {
        if (null == this.first || null == this.first.getNext()) {
            throw new NullPointerException();
        }
        Node pointer = this.first;
        while (true) {
            System.out.println(pointer);
            // 一圈结束。
            if (first == pointer.getNext()) {
                break;
            }
            pointer = pointer.getNext();
        }
    }

    /**
     * 根据用户的输入，计算出圈的顺序。
     *
     * @param start 从第几开始
     * @param nums  数几次
     * @param total 最初总共有多少个
     */
    public void count(int start, int nums, int total) {
        if (null == this.first || 1 > start || start > total) {
            throw new IllegalArgumentException();
        }
        Node pointer = this.first;
        while (first != pointer.getNext()) {
            pointer = pointer.getNext();
        }
        // 先让首节点和辅助指针后移 start - 1 次。
        for (int i = 0; i < (start - 1); i++) {
            first = first.getNext();
            pointer = pointer.getNext();
        }
        // 圈中只有一个节点时退出。
        while (first != pointer) {
            // 让首节点和辅助指针后移 nums - 1 次。
            for (int i = 0; i < (nums - 1); i++) {
                first = first.getNext();
                pointer = pointer.getNext();
            }
            System.out.printf("编号[%d]出圈\n", first.getNo());
            first = first.getNext();
            pointer.setNext(first);
        }
        System.out.printf("圈中剩余编号为[%d] \n", first.getNo());
    }
}

class Node {

    private int no;
    private Node next;

    public Node(int no, Node next) {
        this.no = no;
        this.next = next;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }

    @Override
    public String toString() {
        return "no=" + no;
    }
}

    • 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

    五、结束语

    “-------怕什么真理无穷,进一寸有一寸的欢喜。”

    微信公众号搜索：饺子泡牛奶。

  • 相关阅读:
    maven 多核多线程执行
    计算机网络面试常问问题--保研及考研复试
    Lua类型系统详解(一)
    基于python实现贪心算法、蛮力法、动态规划法解决分数背包问题和0-1背包问题(附完整源码下载)
    基于Java的旅游管理系统设计与实现(源码+lw+部署文档+讲解等)
    是的，诺基亚还“活着”，并推出了新款平板电脑！
    【已解决】ModuleNotFoundError: No module named sklearn
    Java继承的格式
    2022年最新湖北水利水电施工安全员考试题库及答案
    [前端]Preprocessor dependency "less" not found.
  • 原文地址：https://blog.csdn.net/weixin_48776531/article/details/127932545