循环单链表和单链表的区别在于,表中最后一个结点的指针不是NULL,而改为指向头结点,从而整个链表形成一个环。

在循环单链表中,表尾结点*rnext域指向L,故表中没有指针域为NULL的结点,因此,判断循环单链表是否为空的条件不是头结点的指针是否为空,而是它是否等于头指针。

构建一个单向的环形链表思路

  • 先创建第一个结点,让firstNode指向该结点,并形成环形。
  • 后面当我们每创建一个新的结点,就把该结点加入到已有的环形链表中

只有一个结点时

有多个结点时

遍历环形链表的思路

  • 先让一个辅助变量current指向first结点
  • 然后通过一个while循环遍历该环形链表即可。
    current.next == first;时结束

pop出指定结点的思路

  • 需要创建一个辅助指针变量,事先应该指向环形链表的最后这个结点。
  • 报数之前,先让firstNodehelper移动k-1次,从K开始报数
  • 报数时候,让firstNodehelper指针同时移动m-1次;
  • 此时就可以将first指向的结点出圈
  • first = first.next; //把first向后移一位
  • helper.next = first;
    此时,原先first指向的结点会被java的垃圾回收机制回收

代码实现


public class JosephuSolution {
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        // 测试环形链表,
        CircleSingleLinkedList cirList = new CircleSingleLinkedList();
        cirList.initNode(25);
        cirList.showList();
        System.out.println("**********");
        cirList.pop(1, 2, 25);
    }
}

//创建一个环形的单向链表

class CircleSingleLinkedList {
    // 创建一个first结点,当前没有编号
    private JNode firstNode = null;

    // 初始化,构建成一个环形列表
    public void initNode(int nums) {
        // 对nums进行数据校验
        if (nums < 1) {
            System.out.println("nums的值不合法!");
            return;
        }
        JNode currentNode = null;
        // 使用for循环创建环形列表
        for (int i = 1; i <= nums; i++) {
            // 根据编号,创建结点
            JNode tmp = new JNode(i);
            // 如果是第一个结点
            if (i == 1) {
                firstNode = tmp;
                firstNode.setNext(firstNode); // 构成环状
                currentNode = firstNode; // 让辅助指针指向第一个结点
            } else {
                currentNode.setNext(tmp);
                tmp.setNext(firstNode); // 链接到首个结点
                currentNode = tmp;
            }
        }
    }

    // 遍历当前环形列表
    public void showList() {
        // 判断链表是否为空
        if (firstNode == null) {
            System.out.println("链表为空!");
        }
        // 由于firstNode不能动,因此我们仍需要一个辅助指针完成遍历
        JNode currentNode = firstNode;
        while (true) {
            System.out.printf("小孩的编号%d \n", currentNode.getNum());
            if (currentNode.getNext() == firstNode) { // 说明已经遍历完毕
                break;
            }
            currentNode = (currentNode.getNext());
        }
    }

    // 根据用户的输入,计算出出圈的顺序
    /**
     * 
     * @param startNum 表示从第几个结点开始计算
     * @param countNum 表示计算几个
     * @param nums     表示最初有多少个结点
     */
    public void pop(int startNum, int countNum, int nums) {
        // 先对数据进行校验
        if (firstNode == null || startNum < 1 || startNum > nums) {
            System.out.println("所给条件有误!");
            return;
        }

        // 创建一个辅助指针,帮助完成弹出
        JNode helper = firstNode;

        // todo:辅助指针需要指向环形链表的最后结点
        while (true) {
            if (helper.getNext() == firstNode) {
                break;
            }
            helper = helper.getNext();
        }

        // todo:先将firstNode和helper移动
        for (int i = 0; i < startNum - 1; i++) {
            firstNode = firstNode.getNext();
            helper = helper.getNext();
        }

        // 报数时候,让first和helper指针同时移动m-1次,然后出圈
        // 这里是一个循环操作,直到圈中只有一个节点
        while (true) {
            if (helper == firstNode) {
                break;
            }
            // 让first和helper指针同时移动countNum - 1次
            for (int j = 0; j < countNum - 1; j++) {
                firstNode = firstNode.getNext();
                helper = helper.getNext();
            }
            
            //此时first指向的结点,就是要出圈的结点
            System.out.printf("小孩%d出圈。\n",firstNode.getNum());
            
            //将该结点从链表中剔除
            firstNode = firstNode.getNext();
            helper.setNext(firstNode);
        }
        System.out.printf("最后留在圈中的小孩编号为:%d\n",firstNode.getNum());

    }
}

//创建一个Jnode类,表示一个节点
class JNode {
    private int num;
    private JNode next; // 指向下一个结点

    public JNode(int num) {
        this.num = num;
    }

    public int getNum() {
        return num;
    }

    public void setNum(int num) {
        this.num = num;
    }

    public JNode getNext() {
        return next;
    }
    
    public void setNext(JNode next) {
        this.next = next;
    }
}
Last modification:December 10th, 2020 at 11:57 pm
如果觉得我的文章对你有用,请随意赞赏