【数据结构和算法】环形链表

关于链表的新三中形式，环形链表的介绍和代码实现

---

1 环形链表

1.1 约瑟夫问题

• 约瑟夫（Josephu）问题：
  • 设置编号为1，2，3…n个人围坐一圈，约定编号为k（1<=k<=n）的人开始报数，数到m个那个人出列，以此类推，直到所有人都出列，产生一个出队编号序列

• 解决问题：使用环形链表解决

1.2 单向环形链表

1.3 单向环形链表思路

• （1）添加数据
• 创建两个变量，firstNode（第一个节点），curNode（当前最新节点）
• 第一次添加node时，firstNode指向该node，curnode也指向该node，node自身next指向自己形成环状
• 后续添加node时，curNode.next == node，node.next == firstNode，形成环状，并将curNode == node

• （2）遍历数据
• 创建临时node指向firstNode，依次next遍历数据，直到emp.next = first结束循环

1.4 单向环形代码实现

• （1）代码实现

  public class SingleCircularLinkedList {
      //单向节点类
      private class Node {
          public Object data;
          public Node next;
  
          public Node(Object data) {
              this.data = data;
          }
  
          @Override
          public String toString() {
              return "Node{ data = " + data + " }";
          }
      }
  
  
      private Node firstNode; //第一个节点
      private Node curNode; //最新一个节点
  
      /**
       * 添加数据
       * @param data 数据
       */
      public void add(Object data) {
          Node node = new Node(data);
  
          //第一个数据firstNode 和 curNode需要特殊处理
          if(firstNode == null) {
              firstNode = node;
          }
          if(curNode != null) {
              curNode.next = node;
          }
  
          node.next = firstNode;
          curNode = node;
      }
  
      /**
       * 打印单向环形列表
       */
      public void print() {
          Node temp = firstNode;
  
          if (temp == null) {
              System.out.println("链表为空");
              return;
          }
  
          System.out.println("单向环形链表为：");
          do {
              System.out.println(temp);
              temp = temp.next;
          }while(temp != firstNode);
      }
  }

• （2）测试

  @Test
  public void SingleCircularLinkedListTest() {
  	//1. 创建单向环形链表
  	SingleCircularLinkedList linkedList = new SingleCircularLinkedList();
  	linkedList.add(1);
  	linkedList.add(2);
  	linkedList.add(3);
  	linkedList.print();
  }

1.5 约瑟夫问题解决

• （1）思路
• （1）数数，即将firstNode 和 CurNode进行移动，移动m-1次，此时firstNode的位置为出队列位置
• （2）出队列：接将节点删除，直接firstNode向后移（firstNode = firstNode.next），并curNode断开出列节点的指向（curNode.next = first）

• （2）代码实现

  /**
   * 打印约瑟夫问题队列
   * @param start 开始位置
   * @param num 间隔
   */
  public void josephuQueue(int start, int num) {
  	//移动位置
  	int count = 1;
  	while(count != start) {
  		firstNode = firstNode.next;
  		curNode = curNode.next;
  		count ++;
  	}
  
  	System.out.println("约瑟夫问题队列为：");
  	while (curNode != firstNode) {
  		count = 1;
  		//循环报数
  		while(count != num) {
  			firstNode = firstNode.next;
  			curNode = curNode.next;
  			count ++;
  		}
  		//出列（删除节点并打印）
  		System.out.println(firstNode);
  		firstNode = firstNode.next;
  		curNode.next = firstNode;
  	}
  	System.out.println(firstNode);
  }

• （3）测试

  @Test
  public void SingleCircularLinkedListTest() {
  	//1. 创建单向环形链表
  	SingleCircularLinkedList linkedList = new SingleCircularLinkedList();
  	linkedList.add(1);
  	linkedList.add(2);
  	linkedList.add(3);
  	linkedList.add(4);
  	linkedList.add(5);
  	linkedList.print();
  
  	//2. josephu问题
  	linkedList.josephuQueue(1, 2);
  }