CircleLinkedList

2022-12-14
浏览 (554)

CircleLinkedList.java 源码

package datastructure.linkedlist;

/**
 * @author roseduan
 * @time 2019/10/19 22:30
 * @description 循环链表简单实现，约瑟夫问题
 */
public class CircleLinkedList {

    private ListNode head;

    private CircleLinkedList(int val) {
        this.head = new ListNode(val);
        this.head.next = head;
    }

    private static class ListNode{
        int val;
        ListNode next;

        ListNode(int val) {
            this.val = val;
            this.next = null;
        }
    }

    /**
     * 查找
     */
    public ListNode find(int value){
        if (head == null){
            return null;
        }

        ListNode p = head;
        while (p.next != head && p.val != value){
            p = p.next;
        }
        return p;
    }

    /**
     * 插入
     */
    public void add(int value){
        ListNode node = new ListNode(value);
        if (head == null){
            head = node;
            head.next = head;
        }

        ListNode p = head;
        while (p.next != head){
            p = p.next;
        }
        node.next = head;
        p.next = node;
    }

    /**
     * 删除
     */
    public boolean remove(int value) {
        if (head == null){
            return false;
        }
        if (head.next == head && head.val == value){
            head = null;
            return true;
        }
        ListNode prev = null;
        ListNode p = head;
        while (p.next != head && p.val != value){
            prev = p;
            p = p.next;
        }
        //未找到被删除节点
        if (p.val != value){
            return false;
        }
        //删除的是头节点
        if (prev == null){
            ListNode prevHead = head;
            while (prevHead.next != head){
                prevHead = prevHead.next;
            }
            prevHead.next = head.next;
            head = head.next;
            return true;
        }
        prev.next = p.next;
        return true;
    }

    /**
     * 使用循环链表解决约瑟夫问题
     */
    private ListNode survive(int k){
        if (head == null || head.next == head){
            return head;
        }
        int count = 0;
        ListNode p = head;
        while (count++ != k + 1){
            p = p.next;
        }
        remove(p.val);
        return survive(k);
    }

    @Override
    public String toString() {
        StringBuilder result = new StringBuilder();
        ListNode p = head;
        if (p == null){
            return result.toString();
        }

        while (p.next != head){
            result.append(p.val).append(" ");
            p = p.next;
        }
        result.append(p.val);
        return result.toString();
    }
}

你可能感兴趣的文章

DoubleLinkedList

SingleLinkedList

0 赞

所属分类： 后端技术
本文标签： 技术
版权声明： 原创文章如转载，请注明本文链接: https://m.seaxiang.com/blog/7d50bba283064f559537cadb1d66024e

热门推荐

1、直接访问google.com
2、 - 优质文章
3、 gate.io
4、 harmony 鸿蒙hdc使用指导
5、 harmony 鸿蒙初识ArkTS语言
6、 harmony 鸿蒙ArkUI组件（ArkTS）开发常见问题
7、 flink kafka connector scan.startup.mode 的几个选项
8、 golang
9、 openharmony
10、 Vue中input框自动聚焦

Loading...