[循环链表]约瑟夫问题(不健壮版)

使用了自制的LinkedList,不过调用的方法都应该看得懂

算法简介:

  1、通过修改链表节点的next,方便指针后移

  2、算法完成后,整个链表重组,链表头为结果,链表的顺序为删除节点顺序的逆序

  3、ptr:指向需要修改的节点的前一个节点

    helper:需要修改的节点

    newHead:新链表的表头,上一个修改的节点

  4、算法很好懂,我用了冗余的方法,使得算法更容易理解

核心代码如下:

 //链表中有1->8个元素

public int josephus(int key){
  int result=-1;

  FLinkedNode helper;
  FLinkedNode newHead=null;

  FLinkedNode ptr=list.getPreviousNode(key);

  while(true){
    helper=ptr.next();


    if(helper==ptr){
      helper.setNext(newHead);
      newHead=helper;

      result=helper.getKey();
      break;
    }

    ptr.setNext(helper.next());

    helper.setNext(newHead);
    newHead=helper;

    ptr=ptr.step(2);
  }
  return result;
}

原文地址:https://www.cnblogs.com/imakoo/p/3203978.html