# 数据结构---链表及约瑟夫环问题带来的思考

2019/04/10 10:10

JavaLinkedList就是一个双向链表。

``````package com.nijunyang.algorithm.link;

/**
* Description:
* Created by nijunyang on 2020/3/31 22:09
*/
public class MyLinkedList<E> {
private Node<E> head;
private int size = 0;

/**
* 头部插入O(1)
* @param data
*/
public void insertHead(E data){
Node newNode = new Node(data);
newNode.next = head;
head = newNode;
size++;
}

public void insert(E data,int position){
if(position == 0) {
insertHead(data);
}else{
Node cur = head;
for(int i = 1; i < position ; i++){
cur = cur.next;        //一直往后遍历
}
Node newNode = new Node(data);
//
newNode.next = cur.next;        //新加的点指向后面 保证不断链
cur.next = newNode;            //把当前的点指向新加的点
size++;
}

}

public void deleteHead(){
head = head.next;
size--;
}

public void delete(int position){
if(position == 0) {
deleteHead();
}else{
Node cur = head;
for(int i = 1; i < position ; i ++){
cur = cur.next;  //找到删除位置的前一个结点
}
cur.next = cur.next.next; //cur.next 表示的是删除的点，后一个next就是我们要指向的
size--;
}

}

public int size( ){
return size;
}

public String toString( ){
if (size == 0) {
return "[]";
}
StringBuilder sb = new StringBuilder();
sb.append('[');
Node<E> node = head;
sb.append(node.value);
int counter = 0;
for (;;) {
if (++counter == size) {
break;
}
sb.append(",");
node = node.next;
sb.append(node.value);

}
sb.append(']');
return sb.toString();
}

public static void main(String[] args) {
MyLinkedList myList = new MyLinkedList();
myList.insertHead(5);
System.out.println(myList);
myList.insertHead(7);
System.out.println(myList);
myList.insertHead(10);
System.out.println(myList);
myList.delete(0);
System.out.println(myList);
myList.deleteHead();
System.out.println(myList);
myList.insert(11, 1);
System.out.println(myList);

}

private static class Node<E>{

E value;        //值
Node<E> next;        //下一个的指针

public Node() {
}

public Node(E value) {
this.value = value;
}
}
}``````

约瑟夫环问题：

``````package com.nijunyang.algorithm.link;

import java.util.ArrayList;

/**
* Description:
* Created by nijunyang on 2020/3/30 21:49
*/
public class Test {

public static void main(String[] args){
long start = System.currentTimeMillis();
int result = yuesefuhuan_link(70866, 116922);
long end = System.currentTimeMillis();
System.out.println(result);
System.out.println("链表耗时：" + (end - start));
System.out.println("-------------------------");

start = System.currentTimeMillis();
result = yuesefuhuan_arr(70866, 116922);
end = System.currentTimeMillis();
System.out.println(result);
System.out.println("数组耗时：" + (end - start));
}

/**
* 数组约瑟夫环
*/
public static int yuesefuhuan_arr(int n, int m) {
int size = n;
ArrayList<Integer> list = new ArrayList<>(size);
for (int i = 0; i < size; i++) {
list.add(i);
}
int index = 0;
while (size > 1) {
//取模可以回到起点
index = (index + m - 1) % size;
list.remove(index);
size--;
}
return list.get(0);
}

/**
* 循环链表约瑟夫环力扣超时
* @param n
* @param m
* @return
*/
public static int yuesefuhuan_link(int n, int m) {
if (n == 1) {
return n - 1;
}

Node<Integer> headNode = new Node<>(0);
Node<Integer> currentNode = headNode;
//尾结点
Node<Integer> tailNode = headNode;

for (int i = 1; i < n; i++) {
Node<Integer> next = new Node<>(i);
currentNode.next = next;
currentNode = next;
tailNode = currentNode;

}
//成环
tailNode.next = headNode;

//保证第一次进去的时候指向头结点
Node<Integer> remove = tailNode;
Node<Integer> preNode = tailNode;
int counter = n;
while (true) {
for (int i = 0; i < m; i++) {
//一直移除头结点则，前置结点不动
if (m != 1) {
preNode = remove;
}
remove = remove.next;
}
preNode.next = remove.next;
if (--counter == 1) {
return preNode.value;
}
}
}

static class Node<E>{
E value;
Node next;
public Node() {
}
public Node(E value) {
this.value = value;
}
}
}``````

0
0 收藏

0 评论
0 收藏
0