数据结构与算法——链表 Linked List（单链表、双向链表、单向环形链表-Josephu 问题）

2021 年 8 月 27 日
筆記
数据结构与算法

链表是有序的列表，但是在内存中存储图下图所示

链表是以节点的方式来存储，是 链式存储
每个节点包含 data 域、next 域，指向下一个节点
链表的各个节点 不一定是连续存储，如上图所示
链表还分：带头节点、不带头节点，根据实际需求来确定

上面进行了一个简单的介绍，下面分几部分来讲解：

单链表

单链表（带头节点）逻辑结构 示意图如下，当下一个节点为空的时候，该链表就结束了

注意：是逻辑结构，前面说过，在内存中节点不是一个接一个的。

单链表的应用实例

考虑这样一个场景：使用带 head 头的 单向链表 实现水浒英雄排行榜管理

完成对英雄人物的 增删改查 操作
第一种方法：在添加英雄时，直接添加到链表的尾部
第二种方法：在添加英雄时，根据排名将英雄插入到指定位置

如果有这个排名，则添加失败，并给出提示

如上图所示，添加流程。我们创建 HeroNode 节点，他的定义如下

class HeroNode {
  int no;//排名
  String name;
  String nickName;//昵称
  HeroNode next;//指向下一个节点
}

next 指向下一个节点，为空则代表该链表结束。其他的字段则是上面所说的数据了。

单链表-无排序实现

/**
 * 单向链表测试
 */
public class SingleLinkedListDemo {
    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.add(hero1);
        singleLinkedList.add(hero2);
        singleLinkedList.add(hero3);
        singleLinkedList.add(hero4);

        singleLinkedList.list();
    }
}

/**
 * 单向链表
 */
class SingleLinkedList {
    // 头节点，不保存任何数据，只是用来作为一个起始点
    private HeroNode head = new HeroNode(0, "", "");

    /**
     * 添加节点
     *
     *    思路 不考虑编号顺序时：
     *      1. 找到当前链表的最后节点
     *      2. 将最后整个节点的 next 指向新的节点
     * 
     *
     * @param node
     */
    public void add(HeroNode node) {
        // 要遍历到 next 为 null 的时候，才能进行添加
        HeroNode temp = head;
        while (true) {
            // 找到链表的最后,就退出循环
            if (temp.next == null) {
                break;
            }
            //如果没有找到最后, 将将temp后移
            temp = temp.next;
        }
        //当退出while循环时，temp就指向了链表的最后
		//将最后这个节点的next 指向 新的节点
        temp.next = node;
    }

    /**
     * 打印链表中的数据
     */
    public void list() {
        //判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        //因为头节点，不能动，因此我们需要一个辅助变量来遍历
        HeroNode temp = head.next;
        while (true) {
            // 如果是链表的最后
            if (temp == null) {
                break;
            }
            //打印信息
            System.out.println(temp);
            //指针后移，一定要记得
            temp = temp.next;
        }
    }
}

/**
 * 链表中的一个节点：英雄节点
 */
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;
    }

    /**
     * 为了显示方便，重写
     *
     * @return
     */
    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '\'' +
                '}';
    }
}

测试输出

HeroNode{no=1, name='宋江', nickName='及时雨'}
HeroNode{no=2, name='卢俊义', nickName='玉麒麟'}
HeroNode{no=3, name='吴用', nickName='智多星'}
HeroNode{no=4, name='林冲', nickName='豹子头'}

可以看到，已经实现了，如果将 no=4 提前加入

SingleLinkedList singleLinkedList = new SingleLinkedList();
singleLinkedList.add(hero1);
singleLinkedList.add(hero4);  // 提升到这里加入
singleLinkedList.add(hero2);
singleLinkedList.add(hero3);

测试数据如下

HeroNode{no=1, name='宋江', nickName='及时雨'}
HeroNode{no=4, name='林冲', nickName='豹子头'}
HeroNode{no=2, name='卢俊义', nickName='玉麒麟'}
HeroNode{no=3, name='吴用', nickName='智多星'}

编号就是无序的了。下面来实现有序的

单链表-有序实现（从小到大）

添加思路如下：

首先找到新添加节点的位置(新节点遍历比较排名，来查找要插入的位置)，通过辅助变量 temp，然后循环遍历查找
如果有这个排名，则添加失败，并给出提示，没有则进行下面的步骤
新的节点node.next = temp.next
将 temp.next = 新的节点node.next

注：temp辅助节点为要插入点的前一个节点。

简单一点就是：通过排序规则（当前是从小到大）遍历找到要插入的位置，然后改变 next 的指向。

代码实现，在原有的代码基础上新增了一个添加方法，如下

    /**
     * 
     * 添加节点，考虑排序
     *思路：
     *  1. 先找到该节点要添加的位置
     *  2. 通过辅助变量temp改变前一个节点和新节点的 next 指向
     *
     *
     * @param node
     */
    public void addByOrder(HeroNode node) {
        // 由于 head 变量不能动，动了就无法从头遍历了，使用辅助变量来完成我们的添加
        //因为单链表，因为我们找的temp 是位于 添加位置的前一个节点，否则插入不了
        HeroNode temp = head;
        boolean exist = false;  // 添加的节点是否已经在链表中存在，默认为false
        while (true) {
            if (temp.next == null) {
                // 如果是链表尾，则跳出循环
                break;
            }
            // 如果当前节点的 next 编号，大于目标节点（要插入的节点）编号，则找到
            // 应该将目标节点添加到  temp 与 next 之间
            if (temp.next.no > node.no) {
                break;
            }
            // 如果他们相等，则表示链表中已经存在目标节点了
            if (temp.next.no == node.no) {
                exist = true;//添加的节点已经在链表中存在
                break;
            }
            // 没找到，则后移 temp ，继续寻找
            temp = temp.next;
        }

        if (exist) {
            System.out.printf("准备插入的英雄编号 %d 已经存在，不能加入 \n", node.no);
            return;
        }
        // 把节点插入到 temp 和 temp.next 之间
        // temp  ->  node  -> temp.next
        node.next = temp.next;
        temp.next = node;
    }

测试用例如下

    /**
     * 考虑顺序的添加
     */
    public static void test2() {
        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.addByOrder(hero1);
        singleLinkedList.addByOrder(hero4);  // 添加顺序提前
        singleLinkedList.addByOrder(hero2);
        singleLinkedList.addByOrder(hero3);

        singleLinkedList.list();
    }

输出信息

HeroNode{no=1, name='宋江', nickName='及时雨'}
HeroNode{no=2, name='卢俊义', nickName='玉麒麟'}
HeroNode{no=3, name='吴用', nickName='智多星'}
HeroNode{no=4, name='林冲', nickName='豹子头'}

如果重复添加的话，会输出如下类似的信息

准备插入的英雄编号 4 已经存在，不能加入

单链表的修改

在原来的代码基础上新增 update 方法

    /**
     *修改节点的信息, 根据no编号来修改，即no编号不能改.
	 *说明
	 *1. 根据 newNode 的 no 来修改即可
     *
     * @param newNode
     */
    public void update(HeroNode newNode) {
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        //找到需要修改的节点, 根据no编号
		//定义一个辅助变量
        HeroNode temp = head.next;
        boolean exist = false;  // 是否找到要修改的节点
        while (true) {
            // 如果是链表尾部
            if (temp == null) {
                break;
            }
            // 如果已找到
            if (temp.no == newNode.no) {
                exist = true;
                break;
            }
            temp = temp.next;
        }
        // 如果已找到，则修改信息
        if (exist) {
            temp.name = newNode.name;
            temp.nickName = newNode.nickName;
        } else {//没有找到
            System.out.printf("未找到编号为 %d 的英雄", newNode.no);
        }
    }

测试用例

singleLinkedList.addByOrder(hero1);
singleLinkedList.addByOrder(hero4);
singleLinkedList.addByOrder(hero2);
singleLinkedList.addByOrder(hero3);

// 测试修改
System.out.println("修改前");
singleLinkedList.list();
HeroNode hero4New = new HeroNode(4, "林冲-修改测试", "豹子头-修改测试");
singleLinkedList.update(hero4New);

System.out.println("修改后");
singleLinkedList.list();

测试输出

修改前
HeroNode{no=1, name='宋江', nickName='及时雨'}
HeroNode{no=2, name='卢俊义', nickName='玉麒麟'}
HeroNode{no=3, name='吴用', nickName='智多星'}
HeroNode{no=4, name='林冲', nickName='豹子头'}
修改后
HeroNode{no=1, name='宋江', nickName='及时雨'}
HeroNode{no=2, name='卢俊义', nickName='玉麒麟'}
HeroNode{no=3, name='吴用', nickName='智多星'}
HeroNode{no=4, name='林冲-修改测试', nickName='豹子头-修改测试'}

单链表的删除

如上图所示，思路如下：

先找到需要删除的这个节点的 前一个节点 temp

为什么要找到前一个？因为是单向链表，找目标节点就无法完成删除了。
temp.next = temp.next.next
被删除的节点，如果没有其他的引用的话，会被垃圾回收机制回收

    /**
     * 
     *   按编号删除节点
     *   1. 找到要删除的前一个节点
     *   2. 然后将这个前一个节点的 next 指向变更到要删除节点的 next 节点
     * 
     *
     * @param no
     */
    public void delete(int no) {
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        HeroNode temp = head;
        boolean exist = false;  // 是否找到要删除的节点
        while (true) {
            if (temp.next == null) {
                break;
            }
            if (temp.next.no == no) {
                exist = true;
                break;
            }
            temp = temp.next;
        }
        if (!exist) {
            System.out.printf("未找到匹配的编号 %d \n", no);
            return;
        }
        // 删除操作
        temp.next = temp.next.next;
    }

测试代码

System.out.println("删除前");
singleLinkedList.list();
singleLinkedList.delete(1);
singleLinkedList.delete(4);
System.out.println("删除后");
singleLinkedList.list();

输出信息

删除前
HeroNode{no=1, name='宋江', nickName='及时雨'}
HeroNode{no=2, name='卢俊义', nickName='玉麒麟'}
HeroNode{no=3, name='吴用', nickName='智多星'}
HeroNode{no=4, name='林冲', nickName='豹子头'}
删除后
HeroNode{no=2, name='卢俊义', nickName='玉麒麟'}
HeroNode{no=3, name='吴用', nickName='智多星'}

tip：学会思想，将其灵活运用到所需项目中。

单链表面试题

为了加深理解，来看几个面试题

求单链表中有效节点的个数

思路：直接循环统计就行

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

测试用例

@Test
public void lengthTest() {
  System.out.println(singleLinkedList.length());
  singleLinkedList.delete(1);
  System.out.println(singleLinkedList.length());
}

输出

4
3

查找单链表中的倒数第 k 个结点

新浪面试题

    /**
     *
     * 查找单链表中的倒数第k个结点 【新浪面试题】
     *  思路
     *  1. 编写一个方法，接收head节点，同时接收一个index 
     *  2. index 表示是倒数第index个节点
     *  3. 先把链表从头到尾遍历，得到链表的总的长度 getLength
     *  4. 得到size 后，我们从链表的第一个开始遍历 (size-index)个，就可以得到
     *  5. 如果找到了，则返回该节点，否则返回nulll
     *
     * @param index 倒数第几个节点
     * @return
     */
	public static HeroNode findLastIndexNode(HeroNode head, int index) {
		//判断如果链表为空，返回null
		if(head.next == null) {
			return null;//没有找到
		}
		//第一个遍历得到链表的长度(节点个数)
		int size = getLength(head);
		//第二次遍历  size-index 位置，就是我们倒数的第K个节点
		//先做一个index的校验
		if(index <=0 || index > size) {
			return null; 
		}
		//定义给辅助变量， for 循环定位到倒数的index
		HeroNode cur = head.next; //3 // 3 - 1 = 2
		for(int i =0; i< size - index; i++) {
			cur = cur.next;
		}
		return cur;
		
	}

测试用例

@Test
public void findLastIndexNodeTest() {
    //进行测试
		//先创建节点
		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.add(hero1);
		singleLinkedList.add(hero4);
		singleLinkedList.add(hero2);
		singleLinkedList.add(hero3);
    
      System.out.println("查找测试");
      HeroNode lastIndexNode = singleLinkedList.findLastIndexNode(singleLinkedList.getHead(),1);
      System.out.println("查找倒数第 1 个 " + lastIndexNode);
      lastIndexNode = singleLinkedList.findLastIndexNode(singleLinkedList.getHead(),4);
      System.out.println("查找倒数第 4 个 " + lastIndexNode);
      lastIndexNode = singleLinkedList.findLastIndexNode(singleLinkedList.getHead(),2);
      System.out.println("查找倒数第 2 个 " + lastIndexNode);
      lastIndexNode = singleLinkedList.findLastIndexNode(singleLinkedList.getHead(),5);
      System.out.println("查找倒数第 5 个 " + lastIndexNode);
}

输出信息

查找测试
查找倒数第 1 个 HeroNode{no=3, name='吴用', nickName='智多星'}
查找倒数第 4 个 HeroNode{no=1, name='宋江', nickName='及时雨'}
查找倒数第 2 个 HeroNode{no=2, name='卢俊义', nickName='玉麒麟'}
查找倒数第 5 个 null

单链表的反转

腾讯面试题，这个有点难度。

思路：

定义一个新的 reverseHead 节点
从原链表中依次取出节点，并 始终添加到 reverseHead 的第一个节点
将原 head 节点的 next 指向 reverseHead.next

头插法

如下图所示：

//将单链表反转
	public static void reversetList(HeroNode head) {
		//如果当前链表为空，或者只有一个节点，无需反转，直接返回
		if(head.next == null || head.next.next == null) {
			return ;
		}
		
		//定义一个辅助的指针(变量)，帮助我们遍历原来的链表
		HeroNode cur = head.next;
		HeroNode next = null;// 指向当前节点[cur]的下一个节点
		HeroNode reverseHead = new HeroNode(0, "", "");
		//遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead 的最前端
		//动脑筋，这里很重要，
		while(cur != null) { 
			next = cur.next;//先暂时保存当前节点的下一个节点，因为后面需要使用
			cur.next = reverseHead.next;//将cur的下一个节点指向新的链表的最前端
			reverseHead.next = cur; //将cur 连接到新的链表上
			cur = next;//让cur后移
		}
		//将head.next 指向 reverseHead.next , 实现单链表的反转
		head.next = reverseHead.next;
	}

测试用例

@Test
public void reverseTest() {
  System.out.println("翻转前");
  singleLinkedList.list();

  singleLinkedList.reversetList(singleLinkedList.getHead());

  System.out.println("翻转后");
  singleLinkedList.list();
}

输出信息

翻转前
HeroNode{no=1, name='宋江', nickName='及时雨'}
HeroNode{no=4, name='林冲', nickName='豹子头'}
HeroNode{no=2, name='卢俊义', nickName='玉麒麟'}
HeroNode{no=3, name='吴用', nickName='智多星'}
翻转后
HeroNode{no=3, name='吴用', nickName='智多星'}
HeroNode{no=2, name='卢俊义', nickName='玉麒麟'}
HeroNode{no=4, name='林冲', nickName='豹子头'}
HeroNode{no=1, name='宋江', nickName='及时雨'}

从尾到头打印单链表

百度面试题，要求方式：

反向遍历

思路：

反向遍历：使用前面翻转操作后，再打印

有一个问题：会破坏原链表的结构
Stack 栈：利用栈先进后出的特点

该数据结构看后面的博客讲解，这里做个简单的介绍

如上图所示：
1. 入栈操作：数据往 栈底压入
2. 出栈操作：数据从 栈顶弹出
将原链表遍历，以此将每个节点压入栈中，然后遍历栈打印即可

/**
* 
* 逆序打印链表：使用栈先进后出的特点达到要求
* 
*/
public static 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; //cur后移，这样就可以压入下一个节点
		}
		//将栈中的节点进行打印,pop 出栈
		while (stack.size() > 0) {
			System.out.println(stack.pop()); // 出栈，stack的特点是先进后出
		}
	}

测试用例

@Test
public void reversePrintTest(){
  System.out.println("链表数据");
  singleLinkedList.list();
  System.out.println("逆序打印");
  singleLinkedList.reversePrint();
}

输出信息

链表数据
HeroNode{no=1, name='宋江', nickName='及时雨'}
HeroNode{no=4, name='林冲', nickName='豹子头'}
HeroNode{no=2, name='卢俊义', nickName='玉麒麟'}
HeroNode{no=3, name='吴用', nickName='智多星'}
逆序打印
HeroNode{no=3, name='吴用', nickName='智多星'}
HeroNode{no=2, name='卢俊义', nickName='玉麒麟'}
HeroNode{no=4, name='林冲', nickName='豹子头'}
HeroNode{no=1, name='宋江', nickName='及时雨'}

双向链表

单向链表的缺点

从前面的练习题，包括实现单向链表中会发现 单向链表 的以下问题：

查找方向 只能是单向
不能自我删除

需要靠辅助节点，要找到删除节点的上一个节点和删除节点，才能完成删除

而以上问题，双向链表：

可以双向查找
可以自我删除

双向链表分析

双向链表的结构如上图所示，每个节点都有 pre 和 next 变量，所以它可以往前查找或则往后查找。

那么下面先分析下双向链表的：遍历、添加、删除操作思路，之后再去实现：

遍历：和单向链表类似，只是可以双向遍历了
修改：和单向链表一样的方式
添加：默认添加到双向链表的最后一个节点
1. temp.next = newNode
2. newNode.pre = temp
删除

如上图所示，双向链表可以自我删除：
1. 遍历找到要删除的那个节点 temp
2. temp.next.pre = temp.pre
3. temp.pre.next = temp.next

代码实现

可以基于单向链表上的部分代码进行修改。

/**
 * 链表中的一个节点：英雄节点
 */
class HeroNode {
    public int no;
    public String name;
    public String nickName;
    public HeroNode next;// 指向下一个节点, 默认为null
    public HeroNode pre;// 指向前一个节点, 默认为null

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

    /**
     * 为了显示方便，重写
     *
     * @return
     */
    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '\'' +
                '}';
    }
}

/**
 * 双向链表的操作实现
 */
// 创建一个双向链表的类
class DoubleLinkedList {

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

	// 返回头节点
	public HeroNode getHead() {
		return head;
	}

	// 遍历双向链表的方法
	// 显示链表[遍历]
	public void list() {
		// 判断链表是否为空
		if (head.next == null) {
			System.out.println("链表为空");
			return;
		}
		// 因为头节点，不能动，因此我们需要一个辅助变量来遍历
		HeroNode temp = head.next;
		while (true) {
			// 判断是否到链表最后
			if (temp == null) {
				break;
			}
			// 输出节点的信息
			System.out.println(temp);
			// 将temp后移
			temp = temp.next;
		}
	}

	// 添加一个节点到双向链表的最后.
	public void add(HeroNode heroNode) {

		// 因为head节点不能动，因此我们需要一个辅助遍历 temp
		HeroNode2 temp = head;
		// 遍历链表，找到最后
		while (true) {
			// 找到链表的最后
			if (temp.next == null) {
				break;
			}
			// 如果没有找到最后, 将将temp后移
			temp = temp.next;
		}
		// 当退出while循环时，temp就指向了链表的最后
		// 形成一个双向链表
		temp.next = heroNode;
		heroNode.pre = temp;
	}

	// 修改一个节点的内容, 可以看到双向链表的节点内容修改和单向链表一样
	public void update(HeroNode newHeroNode) {
		// 判断是否空
		if (head.next == null) {
			System.out.println("链表为空~");
			return;
		}
		// 找到需要修改的节点, 根据no编号
		// 定义一个辅助变量
		HeroNode temp = head.next;
		boolean flag = false; // 表示是否找到该节点
		while (true) {
			if (temp == null) {
				break; // 已经遍历完链表
			}
			if (temp.no == newHeroNode.no) {
				// 找到
				flag = true;
				break;
			}
			temp = temp.next;
		}
		// 根据flag 判断是否找到要修改的节点
		if (flag) {
			temp.name = newHeroNode.name;
			temp.nickname = newHeroNode.nickname;
		} else { // 没有找到
			System.out.printf("没有找到 编号 %d 的节点，不能修改\n", newHeroNode.no);
		}
	}

	// 从双向链表中删除一个节点,
	// 说明
	// 1 对于双向链表，我们可以直接找到要删除的这个节点
	// 2 找到后，自我删除即可
	public void del(int no) {

		// 判断当前链表是否为空
		if (head.next == null) {// 空链表
			System.out.println("链表为空，无法删除");
			return;
		}

		HeroNode temp = head.next; // 辅助变量(指针)
		boolean flag = false; // 标志是否找到待删除节点的
		while (true) {
			if (temp == null) { // 已经到链表的最后
				break;
			}
			if (temp.no == no) {
				// 找到的待删除节点的前一个节点temp
				flag = true;
				break;
			}
			temp = temp.next; // temp后移，遍历
		}
		// 判断flag
		if (flag) { // 找到
			// 可以删除
			// temp.next = temp.next.next;[单向链表]
			temp.pre.next = temp.next;
			// 这里我们的代码有问题?
			// 如果是最后一个节点，就不需要执行下面这句话，否则出现空指针
			if (temp.next != null) {
				temp.next.pre = temp.pre;
			}
		} else {
			System.out.printf("要删除的 %d 节点不存在\n", no);
		}
	}

}

测试用例：

/**
 * 双向链表测试
 */
public class DoubleLinkedListTest {
    DoubleLinkedList doubleLinkedList;

    @Before
    public void before() {
        HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
        HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");

        // 测试新增
        doubleLinkedList = new DoubleLinkedList();
        doubleLinkedList.add(hero1);
        doubleLinkedList.add(hero4);
        doubleLinkedList.add(hero2);
        doubleLinkedList.add(hero3);
    }

    @Test
    public void addTest() {
        // before 中已测试
    }

    /**
     * 更新测试
     */
    @Test
    public void updateTest() {
        System.out.println("更新前");
        doubleLinkedList.print();
        HeroNode hero4New = new HeroNode(4, "林冲-修改测试", "豹子头-修改测试");
        doubleLinkedList.update(hero4New);
        System.out.println("更新后");
        doubleLinkedList.print();
    }

    /**
     * 删除测试
     */
    @Test
    public void deleteTest() {
        System.out.println("删除前");
        doubleLinkedList.print();
        doubleLinkedList.del(1);
        doubleLinkedList.del(4);
        doubleLinkedList.del(3);
        System.out.println("删除后");
        doubleLinkedList.print();
    }
}

测试输出

更新前
HeroNode{no=1, name='宋江', nickName='及时雨'}
HeroNode{no=4, name='林冲', nickName='豹子头'}
HeroNode{no=2, name='卢俊义', nickName='玉麒麟'}
HeroNode{no=3, name='吴用', nickName='智多星'}
更新后
HeroNode{no=1, name='宋江', nickName='及时雨'}
HeroNode{no=4, name='林冲-修改测试', nickName='豹子头-修改测试'}
HeroNode{no=2, name='卢俊义', nickName='玉麒麟'}
HeroNode{no=3, name='吴用', nickName='智多星'}


删除前
HeroNode{no=1, name='宋江', nickName='及时雨'}
HeroNode{no=4, name='林冲', nickName='豹子头'}
HeroNode{no=2, name='卢俊义', nickName='玉麒麟'}
HeroNode{no=3, name='吴用', nickName='智多星'}
删除后
HeroNode{no=2, name='卢俊义', nickName='玉麒麟'}

课程作业

实现：双向链表的第二种添加方式，按照编号顺序添加

实现和单向添加是一样的

/**
* 
*  按编号顺序添加
*  思路：
*     1. 从头遍历节点，
*     2. 找到比目标大的节点：插入到该节点之前（升序）
*     2. 如果已经存在相同编号的节点，则提示不允许添加
*
* 
*
* @param node
*/
public void addByOrder(HeroNode node) {
  HeroNode temp = head;
  boolean exist = false;  // 添加的节点是否已经在链表中存在，默认false

  while (true) {
    // 已到列表尾部
    if (temp.next == null) {
      break;
    }
    // 已找到
    if (temp.next.no > node.no) {
      break;
    }

    // 已存在该编号
    if (temp.next.no == node.no) {
      exist = true;
      break;
    }
    temp = temp.next;
  }
  if (exist) {
    System.out.printf("准备插入的英雄编号 %d 已经存在，不能加入 \n", node.no);
    return;
  }

  // 把节点插入到 temp 和 temp.next 之间
  // temp  <->  node  <-> temp.next
  node.next = temp.next;//插入的节点的next指向后一个节点
  node.pre = temp;//插入的节点的pre指向前一个节点
  temp.next.pre = node;//插入位置后一个节点的pre指向插入的节点
  temp.next = node;//将插入位置的前一个节点的next指向插入的节点
}

测试用例

@Test
public void addByOrderTest() {
  HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
  HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
  HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
  HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");

  // 测试新增
  doubleLinkedList = new DoubleLinkedList();
  doubleLinkedList.addByOrder(hero1);
  doubleLinkedList.addByOrder(hero4);
  doubleLinkedList.addByOrder(hero2);
  doubleLinkedList.addByOrder(hero3);
  doubleLinkedList.addByOrder(hero3);
  doubleLinkedList.print();
}

测试输出

准备插入的英雄编号 3 已经存在，不能加入 
HeroNode{no=1, name='宋江', nickName='及时雨'}
HeroNode{no=2, name='卢俊义', nickName='玉麒麟'}
HeroNode{no=3, name='吴用', nickName='智多星'}
HeroNode{no=4, name='林冲', nickName='豹子头'}

单向环形链表-Josephu 问题

应用场景-约瑟夫问题

约瑟夫（Josephu）问题，也就是丢手帕问题，他的规则如下

有编号为 1 ~ n 的 n 个人围坐在一起
约定编号为 K( 1 <= k <=n) 的人从 1 开始报数
数到 m 的那个人出列，它的下一位又从 1 开始报数

循环以上过程，直到所有人都出列，并列出出列人的编号。

该问题其实可以使用 单循环链表（单向环形链表）来解决，思路如下：

先构成一个有 n 个节点的单循环链表
然后由 k 节点起从 1 开始计数
计数到 m 时，对应节点从链表中删除，然后从下一个节点又从 1 开始计数

循环以上过程，直到最后一个节点从链表中删除，算法结束

单向环形链表介绍

它的逻辑结构就如下图，形成了一个环状。

约瑟夫问题示意图

需求如下：

n=5：有 5 个人
k=1：从第一个人开始数
m=2：数两次

没有动图，那么使用下面的描述来讲解：

第一轮：2 出队列，1.next = 3

还剩下：1、3、4、5
第二轮：4 出队列，3.next = 5；（从 3 开始报数，第 2 个的出队列，也就是 4）

还剩下：1、3、5
第三轮：1 出队列，5.next = 3

还剩下：3、5
第四轮：5 出队列，3.next = 3

还剩下：3，自己的 next 就是自己
第五轮：3 出队列，队列中无元素，结束

那么最终的出队列顺序就是：2、4、1、5、3

约舍夫问题可以使用数组来解决，这里使用单向环形链表，比较好理解

创建环形链表的思路图解

环形链表添加思路

第 1 个节点被添加进来时

使用一个 first 变量来表示这是第一个节点，和带头节点的链表一样，first节点（也就是头节点）不能去改变他，使用 curBody 变量来辅助我们解决添加的过程，并让 next 指向自己，形成一个环形
第 2 个节点被添加进来时，boy是新要添加进来的节点

将该节点加入到已有的环形变量，并把curBoy指向这个新节点，下面的以此类推
第 3 个节点被添加进来时

遍历环形链表

先让一个辅助变量 curBoy，指向 first 节点 Boy curBoy = first
通过一个 while 循环遍历链表，当 cur.next = first 时，就遍历完了

添加和链表打印代码实现

// 创建一个Boy类，表示一个节点
class Boy {
	private int no;// 编号
	private Boy next; // 指向下一个节点,默认null

	public Boy(int no) {
		this.no = no;
	}

	public int getNo() {
		return no;
	}

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

	public Boy getNext() {
		return next;
	}

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

}

/// 创建一个环形的单向链表
class CircleSingleLinkedList {
	// 创建一个first节点,当前没有编号
	private Boy first = null;

	// 添加小孩节点，构建成一个环形的链表
	public void addBoy(int nums) {
		// nums 做一个数据校验
		if (nums < 1) {
			System.out.println("nums的值不正确");
			return;
		}
		Boy curBoy = null; // 辅助指针，帮助构建环形链表
		// 使用for来创建我们的环形链表
		for (int i = 1; i <= nums; i++) {
			// 根据编号，创建小孩节点
			Boy boy = new Boy(i);
			// 如果是第一个小孩
			if (i == 1) {
				first = boy;
				first.setNext(first); // 构成环
				curBoy = first; // 让curBoy指向第一个小孩
			} else {
				curBoy.setNext(boy);//
				boy.setNext(first);//
				curBoy = boy;
			}
		}
	}

	// 遍历当前的环形链表
	public void showBoy() {
		// 判断链表是否为空
		if (first == null) {
			System.out.println("没有任何小孩~~");
			return;
		}
		// 因为first不能动，因此我们仍然使用一个辅助指针完成遍历
		Boy curBoy = first;
		while (true) {
			System.out.printf("小孩的编号 %d \n", curBoy.getNo());
			if (curBoy.getNext() == first) {// 说明已经遍历完毕
				break;
			}
			curBoy = curBoy.getNext(); // curBoy后移
		}
	}
}

测试用例：

/**
 * 约瑟夫问题测试
 */
public class JosepfuTest {
    /**
     * 添加测试
     */
    @Test
    public void addTest() {
       // 测试一把看看构建环形链表，和遍历是否ok
		CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
		circleSingleLinkedList.addBoy(5);// 加入5个小孩节点
		circleSingleLinkedList.showBoy();
    }
}

测试输出：为了验证前面 5 个小孩的说明是否正确，这里也添加 5 个小孩

小孩的编号 1 
小孩的编号 2 
小孩的编号 3 
小孩的编号 4 
小孩的编号 5

出圈思路分析

还是以这个需求来分析：

用户输入如下：

n=5：有 5 个人
k=1：从第一个人开始数
m=2：数两次

需要一个 辅助节点helper 来帮助出圈，当出圈报数开始时，报数完的时候first所指到的节点出圈，而helper就是来帮助出圈的，如下图所示
将 first 定位到 k ， helper紧随其后（k 从第几个小孩开始报数）

将 first 和 helper 移动 k-1 次
小孩报数时：移动 first 到出圈的节点上，hepler 始终在 first 后面

让 first 和 helper 同时移动 m-1 次，是因为 开始数数的人 也要占用一个位置(自己本身也要数)：比如上图，从 1 开始，first在编号 2 时，就数了 2 下了，它该出圈

小孩出圈（下图是经过报数（2）后的图，原图first在 1 的位置）

先将 first = first.getNext()（first指向下一个节点），然后将 helper.setNext(first)（将出圈小孩的后面一个小孩的next指向变化后的first），那么就如上图所示了，出圈的 first 被孤立出圈了，别人没有引用它了，就会被垃圾回收机制销毁了。

注意：只有 小孩报数和出圈是重复 的，其他的只是这个游戏开始前的一些设置初始化。

出圈代码实现

在原来的环形队列上添加游戏开始方法（计算出圈顺序）

/**
     * 游戏开始，计算出圈顺序
     *
     * @param startNo  从第几个小孩开始数
     * @param countNum 数几下
     * @param nums     参与该游戏的小孩有多少个
     */
    public void countBoy(int startNo, int countNum, int nums) {
        // 进行一个数据校验
        if (first == null ||  // 环形队列没有构建
                countNum < 1 ||  // 每次至少数 1 下
                startNo > nums  // 开始小孩不能大于参与游戏的人数
        ) {
            System.out.println("参数有误，请重新输入");
        }
        // 1. 初始化辅助变量helper到  first 的后面
        //helper用来辅助出圈的
        //先和first指向同一个节点，后通过循环遍历将其指向最后一个节点
        Boy helper = first;
        // 当 helper.next = first 时，就说明已经定位了,helper指向最后小孩节点
        while (helper.next != first) {
            helper = helper.getNext();
        }

        // 2.first 和 helper 同时移动，将first定位在 startNo 位置，helper紧跟其后
        // first 移动到 startNo 位置，同时helper也跟着
        for (int i = 0; i < startNo - 1; i++) {
            first = first.getNext();
            helper = helper.getNext();
        }

        // 为了测试方便，这里添加一个日志输出
        System.out.printf("定位到位置： %d \n", startNo);

        // 3. 开始报数 和 出圈
        while (true) {
            // 当队列中只剩下一个人的时候，跳出循环，因为最后一个必然是他自己出队列
            if (helper == first) {
                break;
            }
            // 报数：移动 m-1 （报数要数自己本身）
            for (int i = 0; i < countNum - 1; i++) {
                // 因为 helper 永远在 first 后面，只要在 first 移动时，指向 first 原来所在的位置即可
                first = first.getNext();
                helper = helper.getNext();
            }
            // 出圈
            System.out.printf("出圈小孩编号 %d \n", first.no);
            //这时将first指向的小孩节点出圈
            first = first.getNext();//将first指向出圈小孩的前面那个小孩
			helper.setNext(first); //将出圈小孩的后面一个小孩的next指向变化后的first
        }
        System.out.printf("最后剩下小孩编号 %d \n", first.getNo());
    }

测试用例

@Test
public void countBoy() {
  CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
		circleSingleLinkedList.addBoy(5);// 加入5个小孩节点
    	System.out.println("构建环形队列");
		circleSingleLinkedList.showBoy();

  // 开始玩游戏
  // 正确的输出顺序为：2、4、1、5、3
  circleSingleLinkedList.countBoy(1, 2, 5);
}

测试输出

构建环形队列
小孩编号 1 
小孩编号 2 
小孩编号 3 
小孩编号 4 
小孩编号 5 
定位到位置： 1 
小孩编号 1 
小孩编号 2 
小孩编号 3 
小孩编号 4 
小孩编号 5 
出圈小孩编号 2 
出圈小孩编号 4 
出圈小孩编号 1 
出圈小孩编号 5 
最后剩下小孩编号 3

可以尝试修改下从第 3 个小孩开始报数

定位到位置： 3 
小孩编号 3 
小孩编号 4 
小孩编号 5 
小孩编号 1 
小孩编号 2 
出圈小孩编号 4 
出圈小孩编号 1 
出圈小孩编号 3 
出圈小孩编号 2 
最后剩下小孩编号 5

小结

需要正视的一个点：现在在学习数据结构，比如数组可以模拟队列，数组可以模拟 环形队列，队列也是一个数据结构，主要是思路。

Tags: 数据结构与算法

数据结构与算法——链表 Linked List（单链表、双向链表、单向环形链表-Josephu 问题）

单链表

单链表的应用实例

单链表-无排序实现

单链表-有序实现（从小到大）

单链表的修改

单链表的删除

单链表面试题

求单链表中有效节点的个数

查找单链表中的倒数第 k 个结点

单链表的反转

从尾到头打印单链表

双向链表

单向链表的缺点

双向链表分析

代码实现

课程作业

单向环形链表-Josephu 问题

应用场景-约瑟夫问题

单向环形链表介绍

约瑟夫问题示意图

创建环形链表的思路图解

环形链表添加思路

遍历环形链表

添加和链表打印代码实现

出圈思路分析

出圈代码实现

小结

VirMach 便宜 VPS

QNews

数据结构与算法——链表 Linked List（单链表、双向链表、单向环形链表-Josephu 问题）

单链表

单链表的应用实例

单链表-无排序实现

单链表-有序实现（从小到大）

单链表的修改

单链表的删除

单链表面试题

求单链表中有效节点的个数

查找单链表中的倒数第 k 个结点

单链表的反转

从尾到头打印单链表

双向链表

单向链表的缺点

双向链表分析

代码实现

课程作业

单向环形链表-Josephu 问题

应用场景-约瑟夫问题

单向环形链表介绍

约瑟夫问题示意图

创建环形链表的思路图解

环形链表添加思路

遍历环形链表

添加和链表打印代码实现

出圈思路分析

出圈代码实现

小结

分享此文：

Related Posts

开源一款超实用的 Dubbo 测试工具，已用半年，感觉很有feel~

Blazor+Dapr+K8s微服务之开发环境调试

有了Swagger2，再也不用为写Api文档头疼了

从350ms到80ms，揭秘阿里工程师 iOS 短视频优化方案

VirMach 便宜 VPS

QNews

熱門文章

熱門搜尋