Making-New-List.md

##Making New List there is a list contains n students'id/ making a new list from this list, starting from taking out the dth student until the original is empty

			   old   new
at first    12345
first time  1235      4
second time 123       45
third time  12        453
fourth      1         4532
last time             45321

####O(n2)暴力解法

import java.util.ArrayList;


public class Solution {

	public ArrayList<Integer> put(ArrayList<Integer> input, int d) {

		ArrayList<Integer> newList = new ArrayList<Integer>();
		while (input.size() != 0) {
			int size = input.size();
			ArrayList<Integer> index = new ArrayList<Integer>();
			for (int i = 0; i < size; i++) {
				if ((i + 1) % d == 0) {
					newList.add(input.get(i));
					index.add(input.get(i));
				}
			}
			for (int i = 0; i < index.size(); i++) {
				input.remove(index.get(i));
			}

			if (size < d) {
				for (int i = size - 1; i >= 0; i--) {
					newList.add(input.get(i));
				}
				return newList;
			}
		}
		return newList;
	}

    public static void main(String[] args) {
    	Solution sol = new Solution();
    	ArrayList<Integer> input = new ArrayList<Integer>();
    	input.add(1);
    	input.add(2);
    	input.add(3);
    	input.add(4);
    	input.add(5);
    	input.add(6);
    	input.add(7);
    	input.add(8);

    	ArrayList<Integer> result = sol.put(input, 4);
    	for (int i = 0; i < result.size(); i++) {
    		System.out.print(result.get(i) +" ");
    	}
    	System.out.println("done");

    }
}

###可以改用linkedlist来解

import java.util.ArrayList;


public class Solution {
	int count = 0;

	private class ListNode {
		private int val;
		private ListNode next;
		ListNode(int val) {
			this.val = val;
		}
	}
	public ArrayList<Integer> put(ArrayList<Integer> input, int d) {
		ArrayList<Integer> result = new ArrayList<Integer>();
		ListNode dummy = new ListNode(0);
		ListNode head = dummy;
		for (Integer i: input) {
			head.next = new ListNode(i);
			head = head.next;
		}
		ListNode pre = dummy;
		head = dummy.next;

		int num = d;
		int size = input.size();
		while(dummy.next != null) {
			head = dummy.next;
			pre = dummy;
			if (size < d) {
				d = size;
			}
			size = 1;
			while (head != null) {
				num = d;
				while (head.next != null && num > 1) {
					head = head.next;
					pre = pre.next;
					num--;
					size++;
				}
				ListNode next = head.next;
				result.add(head.val);
				pre.next = next;
				size--;
				head = head.next;
			}
		}

		return result;
	}

    public static void main(String[] args) {
    	Solution sol = new Solution();
    	ArrayList<Integer> input = new ArrayList<Integer>();
    	input.add(1);
    	input.add(2);
    	input.add(3);
    	input.add(4);
    	input.add(5);
//    	input.add(6);
//    	input.add(7);
//    	input.add(8);

    	ArrayList<Integer> result = sol.put(input, 4);
    	for (int i = 0; i < result.size(); i++) {
    		System.out.print(result.get(i) +" ");
    	}
    	System.out.println("done");
    	System.out.println(sol.count);

    }
}