• 回顾总结之数据结构：3 链表

    这篇主要回顾下，单链表和双链表增删查改的实现，并对约瑟夫问题做了简单思路分析，链表操作一个基本点就是先连结再拆除。
    单链表和双链表中用例都是将一个学生作为节点，包含姓名和分数两项属性，进行相关功能练习，完整代码可访问。https://gitee.com/flying-morning/data-structure/tree/master/src/com/datastructure/list

    class StudentNode {
    public String name; //姓名
    public int score;      //分数
    public StudentNode next;   //指向后一个节点
    public StudentNode pre; //指向前一个节点，双链表的时候才有
    public StudentNode(String name,int score) {
        this.name = name;
        this.score = score;
        next = null;
        pre = null;
    }

    @Override
    public String toString() {
        return "name: " + this.name + ", score: " + this.score;
    }
}

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

    1 单链表

    head 节点：不存放具体数据，作用就是表示单链表头

    1. 1 增加节点

    在末尾插入节点其实没什么好说的，从头节点一直开始遍历，直到找到最后一个节点，然后将尾节点 next 指针指向新节点。
    尾节点：temp.next == null

        public void add(StudentNode student) {
        StudentNode temp = head;
        //next == null 就是尾节点
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = student;
    }

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

    如果是在中间插入节点，比如说按照分数从高到低的顺序。因为单链表只有指向后一个节点的指针，所以我们需要找到插入位置的前一个节点，这样才能进行链表连接操作。
    比如我们要插入的节点 a3 分数高于 a2，所以要插到 a2 之前，那么 a1 这个节点就是我们需要找到的，有如下两步操作：

    • a3.next = a1.next，将新节点 a3 的 next 指向 a2，而 a2 = a1.next
    • a1.next = a3，将 a1 的 next 指向 a3.
      这两步顺序不能反，否则会丢失 a2 节点的访问
      在这里插入图片描述
    	public void addByScore(StudentNode studentNode) {
        StudentNode temp = head;
        while (temp.next != null) {
            //目标节点的分数大于后一个节点
            if(temp.next.score < studentNode.score) {
                break;
            }
            temp = temp.next;
        }
        //节点插入，先将目标节点的next指向temp.next
        //再将 temp.next 指向目标节点
        studentNode.next = temp.next;
        temp.next = studentNode;
    }

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

    1. 2 删除节点

    删除节点大概三步：

    • delNode = a1.next,暂存 a3，不暂存的话，后面就找不到这个节点了。
    • a1.next = a1.next.next，让 a1 的 next 指向 a2
    • delNode.next = null，将 a3 的 next 置为 null，完全断开

    在这里插入图片描述

    	public void del(String name) {
        StudentNode temp = head;
        while (temp.next != null) {
            if (temp.next.name.equals(name)) {
                break;
            }
            temp = temp.next;
        }
        if (temp.next != null) {
            StudentNode delNode = temp.next;
            temp.next = temp.next.next;
            delNode.next = null;
            System.out.println(name + "已被删除");
        }else {
            System.out.println(name + "不在链表中");
        }
    }

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

    1.3 修改和查找

    这两个其实没什么好说的，同增加和删除不同，这里因为不需处理跟前后节点的关系，所以只需要当前节点就行，我们在遍历的时候就让 StudentNode temp = head.next;，不再记录前置节点的信息了。

    2 双链表

    2.1 增加节点

    在末尾增加，和单链表类似，只是多了将新增节点的 pre 指向之前的尾节点的操作。

    	public void add(StudentNode studentNode) {
        StudentNode temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = studentNode;
        studentNode.pre = temp;
    }

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

    按分数插在中间，比单链表要简单，步骤如下

    • a3.next = a2; a2.pre = a2.pre，这一步就处理了好了 a3 节点 pre 和 next 的值
    • a2.pre.next = a3,将 a1 的 next 指向 a3；a2.pre = a3，将 a2 的 pre 指向 a3

    在这里插入图片描述

    代码中的 temp 就想当于 a2

    	public void addByScore(StudentNode studentNode) {
        StudentNode temp = head.next;
        while (temp != null) {
            // 目标节点的分数大于当前节点
            if(temp.score < studentNode.score) {
                break;
            }
            temp = temp.next;
        }
        //节点插入
        studentNode.next = temp;
        studentNode.pre = temp.pre;
        temp.pre.next = studentNode;
        temp.pre = studentNode;
    }

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

    2.2 删除节点

    删除 a3 节点，主要步骤如下：

    • 先连结：a3.pre.next = a3.next; a3.next.pre = a3.pre，借助 a3 的信息将 a1、a2关联
    • 断开a3：a3.next = null; a3.pre = null

    在这里插入图片描述

        public void del(String name) {
        StudentNode temp = head.next;
        while (temp != null) {
            if (temp.name.equals(name)) {
                break;
            }
            temp = temp.next;
        }
        if(temp != null) {
            temp.pre.next = temp.next;
            if (temp.next != null) {
                temp.next.pre = temp.pre;
                temp.next = null;
            }
            temp.pre = null;
            System.out.println(name + "已被删除");
        }else {
            System.out.println(name + "不在链表中");
        }
    }

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

    3 单向环形链表

    环形链表的一个特点就是，尾节点的 next 指向第一个节点，形成一个环状的结构。我们定义第一个添加的节点为 first ，且只有一个节点时 first.next = first成立。

    这里主要围绕约瑟夫问题展开，每个节点只有 num 这一个属性，表示序号，方便问题求解。

    class NumNode {
    int num; //节点序号
    NumNode next;
    NumNode(int num) {
        this.num = num;
        this.next = null;
    }
}

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

    节点的操作在前面应该已经很熟悉了，这里主要讲讲约瑟夫问题怎么解。
    对于如下的环形链表，first 指向 a1，startNum=3 表示从 3 号节点开始报数，countNum=3 表示数到 3 时停止，且该节点被删除。
    在这里插入图片描述
    下面是一个求解思路：
    在这里插入图片描述

    （1）该问题需要不断从链表中删除节点，对于单向链表，删除节点是需要前一个节点信息的，因此增加一个辅助节点 last ，始终表示 first 的前一个位置，这样在做删除 first 节点操作的时候，执行 last.next = first.next 就可以了。

        private NumNode lastNode(NumNode first) {
        NumNode curNode = first; //辅助遍历
        while(curNode.next != first) { //next == first 时就是目标节点
            curNode = curNode.next;
        }
        return curNode;
    }

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

    （2）根据 startNum 移动 first 到开始位置，last 也跟着移动。

            //将first移动到开始报数的位置
        while (startNum > 1) { //
            lastNode = lastNode.next;
            first = first.next;
            --startNum;
        }

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

    （3）第二步完成后，从 first 所在的位置开始报数，数countNum 下，这一过程中向后移动 first、last 两个节点，然后对 first 节点做删除操作，并找到新的 first 节点。

            while (first != lastNode) { //只有一个节点时退出
            int mCountNum = countNum;
            while (mCountNum > 1) { //开始报数，数 countNum下
                lastNode = lastNode.next;
                first = first.next;
                --mCountNum;
            }
            //此时要删除的节点就是 first
            System.out.print("移除节点：" + first.num);
            lastNode.next = first.next;
            first = first.next;
            System.out.println(", 当前链表为：");
            show();
        }

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

    （3）重复第（3）步中的过程，直到只剩下一个节点。

    最后附上全部代码吧。

    package com.datastructure.list;

public class JosepFu {
    public static void main(String[] args) {
        CycleLinkedList cycleLinkedList = new CycleLinkedList(5);
        cycleLinkedList.show();
        cycleLinkedList.solveJospFu(3,3);
    }
}

class CycleLinkedList {
    NumNode first;
    CycleLinkedList(int totalNum) {
        if (totalNum < 1) {
            System.out.println("totalNum < 1,创建失败");
            return;
        }
        //定义首节点
        first = new NumNode(1);
        first.next = first;
        //其他节点
        NumNode curNode =first;
        for (int i=2; i <= totalNum; ++i) {
            NumNode node = new NumNode(i);
            curNode.next = node;
            node.next = first;
            curNode = curNode.next;
        }
    }
    public void show() {
        if (first == null) {
            System.out.println("环形链表为空");
        }
        NumNode curNode = first;
        do {
            System.out.println("节点编号: " + curNode.num);
            curNode = curNode.next;
        } while (curNode != first);
    }

    /**
     *
     * @param startNum 从第几个节点开始报数
     * @param countNum 数几下 countNum
     */
    public void solveJospFu(int startNum,int countNum) {
        if (first == null) {
            return;
        }
        NumNode lastNode = lastNode(first); //辅助节点删除操作

        //将first移动到开始报数的位置
        while (startNum > 1) { //
            lastNode = lastNode.next;
            first = first.next;
            --startNum;
        }

        //
        while (first != lastNode) { //只有一个节点时退出
            int mCountNum = countNum;
            while (mCountNum > 1) { //开始报数，数 countNum下
                lastNode = lastNode.next;
                first = first.next;
                --mCountNum;
            }
            //此时要删除的节点就是 first
            System.out.print("移除节点：" + first.num);
            lastNode.next = first.next;
            first = first.next;
            System.out.println(", 当前链表为：");
            show();
        }

    }

    /**
     * 找到 first 节点的前一个节点
     * @param first 第一个节点
     * @return first 节点的前一个节点
     */
    private NumNode lastNode(NumNode first) {
        NumNode curNode = first; //辅助遍历
        while(curNode.next != first) { //next == first 时就是目标节点
            curNode = curNode.next;
        }
        return curNode;
    }

}
class NumNode {
    int num; //节点序号
    NumNode next;
    NumNode(int num) {
        this.num = num;
        this.next = 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
    • 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
  • 相关阅读:
    安装clang
    零基础html学习/刷题-第一期
    java计算机毕业设计小学生素质成长记录平台源码+系统+数据库+lw文档+mybatis+运行部署
    Qt-day3
    “论数据访问层设计技术及其应用”写作框架，系统架构设计师
    如何调用本地 json 文件数据
    Day02_《MySQL索引与性能优化》
    leetcode---距离计算
    【零基础学Python】后端开发篇 第二十一节--Python Web开发二：Django的安装和运行
    使用nvm切换node方法，以及在nvm中的注意事项
  • 原文地址：https://blog.csdn.net/hejnhong/article/details/125436221