数据结构和算法--3链表（单向链表、双向链表、环形单向链表和约瑟夫问题）

链表

链表是以节点的方式来存储
每个节点包含data域和next域，指向下一个节点
链表的各个节点不一定是连续存储
链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定

单向列表

最大特点是可以将物理地址上不连续的数据连接起来，通过指针来对物理地址进行操作，实现增删改查等功能。

单链表分为两种：有头链表和无头链表。

有头节点的增删改查

定义一个单链表的类：

//定义一个SingleLinkedList,单链表,管理HeroNode
class SingleLinkedList{
    //初始化一个头节点，没有具体的值，只是表示是单链表的开头
    private HeroNode head = new HeroNode(0, "", "");

无序添加图解和思路：

 代码实现：

//向单链表中添加节点
    //1不考虑编号顺序时！！
    //找到当前链表的末节点，末节点的next指向新节点
    public void addNode(HeroNode heroNode) {
        //头节点不能动，需要一个辅助节点去进行遍历，代表的是指向哪个节点
        HeroNode temp = head;
        //遍历链表，找到最后
        while(true) {
            //当头节点后面没有值，说明已经到达单链表末尾
            if(temp.next == null) {
                break;
            }
            //当没有到单链表末尾，每循环一次就把指针向后移动一位
            temp = temp.next;
        }
        //当跳出循环，说明一定temp已经指向单链表末尾
        //temp.next指向传入的heroNode节点
        temp.next = heroNode;
    }

有序添加图解和思路：

代码实现：

//向单链表中添加节点
    //2考虑编号顺序，根据排名把节点添加到指定位置！！
    public void addOrder(HeroNode heroNode) {
        //同样需要一个辅助节点来帮助找到要添加的位置
        //因为是单链表，temp表示的是添加位置的前一个节点，然后把temp.next指向heroNode
        HeroNode temp = head;
        //flag标志要添加的编号在链表中是否已经存在
        boolean flag = false;
        while(true) {
            //表示已经到链表的末尾
            if(temp.next == null) {
                break;
            }
            //如果辅助节点的下个节点的编号比新节点的大，新节点放在辅助节点的后面（辅助节点下一个节点的前面）
            if(temp.next.no > heroNode.no) {
                break;
                //如果辅助节点的下一个节点编号与新节点相同，说明已存在
            }else if(temp.next.no == heroNode.no){
                flag = true;
                break;
            }
            //如果没有找到，辅助节点向后移动一位
            temp = temp.next;
        }
        //判断flag的值来向控制台输出语句
        if(flag) {
            System.out.printf("您输入的编号为%d的英雄已存在，不能重复添加\n",heroNode.no);
        }else {
            //把辅助节点的后一个节点绑定到新节点的后面
            heroNode.next = temp.next;
            //把新节点放到辅助节点的后一个节点上
            temp.next = heroNode;
        }
    }

修改节点信息的代码实现：

//修改节点信息，根据no编号来修改
    public void updateNode(HeroNode heroNode) {
        //判断是否为空
        if(head.next == null) {
            System.out.println("当前链表为空");
            return;
        }
        //不为空时，通过辅助节点依次遍历
        HeroNode temp = head.next;
        //判断是否找到节点
        boolean flag = false;
        while(true) {
            //如果辅助节点后面为空，说明已经到了链表末尾
            if(temp.next == null) {
                break;
            }
            //如果辅助节点编号等于给定节点的编号，找到了
            if(temp.no == heroNode.no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        //根据flag判断是否找到
        if(flag) {
            temp.name = heroNode.name;
            temp.nickname = heroNode.nickname;
        }else {
            System.out.printf("没有找到编号为%d的英雄\n",heroNode.no);
        }
    }

删除节点思路：

1.我们先找到需要删除的这个节点的前一个节点
 2.temp.next = temp.next.next
 3.被删除的节点没有其他引用指向，会被垃圾回收机制回收

代码实现：

//删除节点
    public void delete(int no) {
        //头节点不能动，需要一个辅助节点找到要删除节点的前一个节点
        HeroNode temp = head;
        //是否找到要删除节点的前一个节点
        boolean falg = false;
        while(true) {
            //表示已经遍历到链表末尾
            if(temp.next == null) {
                break;
            }
            //如果temp.next.no==no，此时temp节点就是要删除节点的前一个节点
            if(temp.next.no == no) {
                falg = true;
                break;
            }
            temp = temp.next;
        }
        if(falg) {
            temp.next = temp.next.next;
        }else {
            System.out.printf("要删除的%d节点不存在\n",no);
        }
    }

遍历节点：

//显示单链表的数据，通过遍历
    public void list() {
        //如果头节点后面没有值，链表为空
        if(head.next == null) {
            System.out.println("当前链表为空");
            return;
        }
        //通过辅助变量来遍历
        HeroNode temp = head.next;
        while(true) {
            //当temp为空，说明已经到达单链表末尾
            if(temp==null) {
                break;
            }
            //输出节点的信息
            System.out.println(temp);
            //将temp后移一位
            temp = temp.next;
        }
    }
}

创建节点类

//定义HeroNode，每个HeroNode对象就是一个节点
class HeroNode{
    //节点的指针编号
    public int no;
    public String name;
    //别名
    public String nickname;
    //指向下一个节点
    public HeroNode next;
    public HeroNode(int no, String name, String nickname) {
        this.no = no;
        this.name = name;
        this.nickname = nickname;
    }
    @Override
    public String toString() {
        return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
    }

对单向链表进行测试：

public static void main(String[] args) {
        //创建节点
        HeroNode hero1 = new HeroNode(1, "宋江", "宋江");
        HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
        HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
        //将节点添加到单链表中
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        //不考虑排名，直接放入节点
//        singleLinkedList.addNode(hero1);
//        singleLinkedList.addNode(hero2);
//        singleLinkedList.addNode(hero3);
//        singleLinkedList.addNode(hero4);
        //考虑排名问题，按顺序添加
        singleLinkedList.addOrder(hero4);
        singleLinkedList.addOrder(hero2);
        singleLinkedList.addOrder(hero1);
        singleLinkedList.addOrder(hero3);
        singleLinkedList.list();
        //修改节点信息
        HeroNode newHeroNode = new HeroNode(2, "小卢", "玉麒麟~~");
        singleLinkedList.updateNode(newHeroNode);
//        遍历链表
        singleLinkedList.list();
        //删除某个节点
        singleLinkedList.delete(1);
        singleLinkedList.list();
    }

单向链表练习题

1获取单链表中有效节点的个数

代码实现

//获取单链表中有效节点的个数
    //head 链表的头节点
    public int getLength(HeroNode head) {
        //如果头节点后面为空，则这个一个空链表
        if(head.next == null) {
            return 0;
        }
        int length = 0;
        //需要一个辅助节点来帮忙遍历链表
        HeroNode temp = head.next;
        //如果辅助节点的下一个节点不为空，有效节点个数+1；
        while(temp!= null) {
            length++;
            temp = temp.next;
        }
        return length;
    }

测试类：

　　　　　//获取单链表中节点个数
        //获取头节点
        HeroNode head = singleLinkedList.getHead();
        int length = singleLinkedList.getLength(head);
        System.out.println("获取到的节点个数为"+length);

2查找单链表中倒数第k个节点

思路：

1.编写一个方法，接收head及节点，同时接收index
2.index表示的是倒数第index节点
3.先把链表全部遍历一遍，得到有效的节点个数length（链表的长度）
4length-index就是这个倒数第k个节点的位置
5.找到就返回节点信息，找不到返回空

代码实现：

//查找单链表中倒数第k个节点
    public HeroNode findLastIndexNode(HeroNode head,int index) {
        //如果头节点后为空，这是一个空链表
        if(head.next == null) {
            return null;
        }
        //拿到链表中所有节点的个数（链表的长度）
        int size = getLength(head);
        //查找倒数第k个节点（size-index）的位置
        //判断index是否是合法数据
        if(index <= 0 || index > size) {
            return null;
        }
        //通过辅助节点帮我们遍历到倒数第k个节点的位置,temp初始值为第一个有效节点
        HeroNode temp = head.next;
        //需要遍历的次数
        for(int i = 0;i < (size-index);i++) {
            temp = temp.next;
        }
        return temp;
    }

测试类

//查找单链表中倒数第k个节点
   HeroNode res = singleLinkedList.findLastIndexNode(head, 2);
   System.out.println("倒数的节点信息为"+res);

3反转单链表

思路：

1.先定义一个节点 HeroNode reverseHead = new HeroNode()
2.从头到尾遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead的最前端
3.原来的链表head.next = reverseHead.next

代码实现：

//单向链表反转
    public void reverseList(HeroNode head) {
        //如果当前列表为空，或只有一个节点，直接返回，无需遍历
        if(head.next == null || head.next.next==null) {
            return;
        }
        //定义一个辅助节点，来帮忙遍历原链表
        HeroNode cur = head.next;
        //当把当前节点拿走时，整个链表断开了，所以要在移走前把后一个节点保存起来
        HeroNode next = null;
        //新链表
        HeroNode reverseHead = new HeroNode(0, "", "");
        //遍历原链表，辅助节点走到哪，就把节点拿出来放在新链表下
        while(cur != null) {
            //把当前节点的后一个节点的值获取出来，防止当前拿走后后面的节点取不到值
            next = cur.next;
            //此时把当前节点拿出来，这个节点的后一个节点应该是新链表当前的下一个节点
            cur.next = reverseHead.next;
            //然后现在再把新链表的后一个节点指向cur
            reverseHead.next = cur;
            //指针向后移动一位接着遍历
            cur = next;
        }
        //当跳出while循环说明已经都反转了，再把原链表的后一个节点直接等于新链表的后一个节点，得出的数据还是在原链表下
        head.next = reverseHead.next;
    }

测试类

　HeroNode head = singleLinkedList.getHead();
       singleLinkedList.reverseList(head);
       singleLinkedList.list();

4倒序打印单链表

思路：

方式一：
先将单链表进行反转操作，然后再进行遍历即可，但是这样会破坏原来单链表的访问，不推荐
方拾二：
可以利用栈这个数据结构，将各个节点压入到栈中，然后利用栈的先进后出的特点，实现逆序打印的效果

代码打印：

//逆序打印
    //利用栈这个数据结构，将各个节点压入到栈中，然后利用栈的先进后出的特点，实现逆序打印的效果
    public void reversePrint(HeroNode head) {
        //先判断是否为空链表
        if(head.next ==null) {
            return;
        }
        Stack<HeroNode> stack = new Stack<HeroNode>();
        //借助辅助节点，帮忙遍历
        HeroNode cur = head.next;
        while(cur != null) {
            //只要辅助节点有值，就把它压在栈内
            stack.push(cur);
            cur = cur.next;
        }
        //从栈中取值
        while(stack.size() >0) {
            System.out.println(stack.pop());
        }
    }

测试类

//倒序打印链表
    System.out.println("倒序打印链表");
    singleLinkedList.reversePrint(head);

5合并两个有序的单链表，合并之后的链表依然有序

双向列表

双向链表的遍历，添加，修改，删除的思路

添加节点（默认添加到双向链表的最后）

思路

先找到双向链表的最后节点
temp.next = newHeroNode
newHeroNode.pre = temp

无序添加

//1不考虑编号顺序时！！
    //找到当前链表的末节点，末节点的next指向新节点
    public void addNode(HeroNode2 heroNode) {
        //头节点不能动，需要一个辅助节点去进行遍历，代表的是指向哪个节点
        HeroNode2 temp = head;
        //遍历链表，找到最后
        while(true) {
            //当头节点后面没有值，说明已经到达单链表末尾
            if(temp.next == null) {
                break;
            }
            //当没有到单链表末尾，每循环一次就把指针向后移动一位
            temp = temp.next;
        }
        //当跳出循环，说明一定temp已经指向单链表末尾
        //temp.next指向传入的heroNode节点,heroNode的前一个节点是temp，反指向回temp，完成双向链接
        temp.next = heroNode;
        heroNode.pre = temp;
    }

有序添加

//2考虑编号顺序，根据排名把节点添加到指定位置！！
    public void addOrder(HeroNode2 heroNode) {
        //同样需要一个辅助节点来帮助找到要添加的位置
        HeroNode2 temp = head;
        //flag标志要添加的编号在链表中是否已经存在
        boolean flag = false;
        while(true) {
            //表示已经到链表的末尾
            if(temp.next == null) {
                break;
            }
            //如果辅助节点的下个节点的编号比新节点的大，新节点放在辅助节点的后面（辅助节点下一个节点的前面）
            if(temp.next.no > heroNode.no) {
                break;
                //如果辅助节点的下一个节点编号与新节点相同，说明已存在
            }else if(temp.next.no == heroNode.no){
                flag = true;
                break;
            }
            //如果没有找到，辅助节点向后移动一位
            temp = temp.next;
        }
        //判断flag的值来向控制台输出语句
        if(flag) {
            System.out.printf("您输入的编号为%d的英雄已存在，不能重复添加\n",heroNode.no);
        }else {
//            把heroNode绑定到temp的后面
            heroNode.next = temp.next;
            if(temp.next != null) {
            temp.next.pre = heroNode;
            }
            //双向链表，heroNode反向绑定
            temp.next = heroNode;
            heroNode.pre = temp;
            
        }
    }

修改和遍历与单向链表思路一样

删除节点

思路：

双向链表可以实现自我删除，不用再去找它的前一个节点
直接找到要删除的节点temp
temp.pre.next= temp.next
temp.next.pre = temp.pre

//删除节点
    public void delete(int no) {
        //头节点不能动，需要一个辅助节点找到要删除节点的前一个节点
        HeroNode2 temp = head.next;
        if(temp == null) {
            System.out.println("此双向链表是个空链表");
            return;
        }
        //是否找到要删除节点的前一个节点
        boolean falg = false;
        while(true) {
            //表示已经遍历到链表末尾
            if(temp == null) {
                break;
            }
            //如果temp.no==no，此时temp节点就是要删除的节点
            if(temp.no == no) {
                falg = true;
                break;
            }
            temp = temp.next;
        }
        if(falg) {
            temp.pre.next = temp.next;
            //判断是否删除的是最后一个节点，因为最后一个节点的的temp.next为空没有pre属性,会报空指针
            if(temp.next != null) {
                temp.next.pre = temp.pre;
            }
        }else {
            System.out.printf("要删除的%d节点不存在\n",no);
        }
    }

环形单向链表

 构建单向环形链表

思路：

1.先创建一个节点，让first指向该节点，并形成环形
2后面每创建一个节点，就把该节点加入到已有的环形链表中

代码实现：

//创建一个小孩类
class Child{
    //小孩编号
    private int no;
    //下一个小孩
    private Child next;
    //有参构造
    public Child(int no) {
        this.no = no;
    }
    public int getNo() {
        return no;
    }
    public void setNo(int no) {
        this.no = no;
    }
    public Child getNext() {
        return next;
    }
    public void setNext(Child next) {
        this.next = next;
    }
    @Override
    public String toString() {
        return "Child [no=" + no + ", next=" + next + "]";
    }

//创建一个first节点，后面会用到
    private Child first = null;
    //添加小孩节点,参数nums表示总共有多少个小孩
    public void add(int nums) {
        //判断nums的符合条件
        if(nums < 1) {
            System.out.println("您输入的数字不符合环形单向链表的条件");
            return;
        }
        //因为第一个节点不能动，需要一个辅助节点帮忙遍历
        Child cur = null;
        //当输入的nums符合条件时，for循环创建环形单向链表
        for(int i = 1;i <= nums;i++) {
            Child child = new Child(i);
            //如果是第一个节点
            if(i == 1) {
                first = child;//第一个节点不动
                first.setNext(first);//环形需要自己指向自己
                cur = first;//让辅助节点指向第一个节点
            }else {
                cur.setNext(child);//辅助节点就代表当前的那个节点
                child.setNext(first);//每添加后都要指向第一个节点形成环形链表
                cur = child;//辅助指针后移
            }
        }

遍历环形链表

思路：

1先让辅助指针cur指向first节点
2通过while循环遍历该环形链表，当cur.next = first结束

代码实现：

//遍历环形链表
    public void showChild() {
        //判断链表是否为空
        if(first == null) {
            System.out.println("当前环形链表为空");
            return;
        }
        //遍历时仍需借助辅助节点进行遍历
        Child cur = first;
        while(true) {
            System.out.printf("小孩编号为%d\n",cur.getNo());
            //判断是否是最后一个节点
            if(cur.getNext() == first) {
                break;
            }
            cur = cur.getNext();
        }
    }

约瑟夫问题

什么是约瑟夫问题？

设编号为1,2...n的n个人围坐一圈，约定编号k（1<= k <= n）的人从1开始报数，数到m的那个人出列，它的下一位从1开始报数，数到m的那个人再次出列，依次循环直到所有人出列为止，由此产生一个出队编号的序列

思路：

k=？代表从第几个人开始数数
m=？代表数几下
n=？代表总共有多少人

1需要创建一个辅助指针helper，事先应该让辅助指针指向环形链表的最后一个节点
2让first和helper移动k-1的位置，first表示从哪个人开始数，helper依旧在最后一个节点
3让first和helper同时移动m-1次，
4让first指向的人出圈
5需要把first向后移动一位，然后由helper指向first，这样要出圈的人没有人指向它，会被回收

代码实现：

//约瑟夫问题，小孩出圈，startNo从第几个人开始数数，countNum数几下，nums总多少人
    public void outChild(int startNo,int countNum,int nums) {
        add(nums);
        //判断是否符合条件
        if(startNo < 1 ||first == null || startNo > nums) {
            return;
        }
        //1需要创建一个辅助指针helper，事先应该让辅助指针指向环形链表的最后一个节点
        Child helper = first;
        while(true) {
            if(helper.getNext() == first) {
                break;
            }
            helper = helper.getNext();
        }
        //2让first和helper移动k-1的位置，first表示从哪个人开始数，helper依旧在最后一个节点
        for(int j = 0;j < startNo-1;j++) {
            first = first.getNext();
            helper = helper.getNext();
        }
        //3让first和helper同时移动m-1次
        while(true) {
            //如果只剩下一个人
            if(first == helper) {
                break;
            }
            for(int j = 0;j < countNum - 1;j++) {
                first = first.getNext();
                helper = helper.getNext();
            }
            //4让first指向的人出圈
            System.out.printf("小孩%d出圈\n",first.getNo());
            //5.需要把first向后移动一位，然后由helper指向first，这样要出圈的人没有人指向它，会被回收
            first = first.getNext();
            helper.setNext(first);

        }
        System.out.printf("最后留在圈中的人是%d\n",first.getNo());
    }

。