LinkedList和Arrays的練習

LinkedList練習）

• 插入節點
• 在原有連結清單的基礎上逆轉元素順序
• 在數組指定位置插入元素
• 在原數組上逆轉元素
• 無題

插入節點

在以下代碼的基礎上完成插入節點的功能。例如：

5–6--2，insert (10,1) result in 5–10–6--2.

這裡的position是從0開始的

public class SLList{
	private class IntNode{
		public int item;
		public IntNode next;
		public IntNode(int item, IntNode next){
			this.item = item;
			this.next = next;
			}
		}
		
		private IntNode first;
		
		public void addFirst(int x){
			first = new IntNode(x, first);
			}
		}
	
           

插入節點代碼如下：

public void insert(int item, int position){
	if(first == null || position ==0){
		addFirst(item);
		return;
	}
	IntNode currentNode = first;
	while(position > 1 && currentNode.next != null){
		position--;
		currentNode = currentNode.next;
		}
		IntNode newNode = new IntNode(item,currentNode.next);
		current.next = newNode;
	}
		
           

在原有連結清單的基礎上逆轉元素順序

疊代解法（reverse iteratively）

public void reverse(){
	IntNode frontOfRevered = null;
	IntNode nextNodeToAdd = first;
	while(nextNodeToAdd != null){
		IntNode remainderOfOriginal = nextNodeToAdd.next;
		nextNodeToAdd.next = frontOfRevered;
		frontOfReversed = nextNodeToAdd;
		nextNodeToAdd = remainderOfOriginal;
		}
		first  = frontOfReversed;
	}
		
           

第一二句設定是因為：對于一條原始的鍊，下一個要加上的節點就是第一個，而在第一個節點之前已經被擰轉的是空節點（因為沒有啊）！第三句，因為要把第一個節點擰到後面了，是以先把第一個節點的後續節點儲存下來。第四句，因為上一句已經把要擰轉的節點的後續節點保留了，現在可以把這個節點的後續改為上一個已經擰轉的節點了。第五句，經過第四句，現在處理的節點也已經變成了逆轉鍊的頭部。而下一個要逆轉的節點就是保留的那個節點。這個循環結束的情況是要處理的節點不為空。

遞歸寫法（ recursion）

public void reverse(){
	first = reverseRecursiveHelper(first);
	}

private IntNode reverseRecursiveHelper(IntNode front){
	if(front ==null || front.next == null){
		return front;
		}else{
		IntNode reversed = reverseRecursiveHelper(front.next);
		front.next.next = front;
		front.next =null;
		return reversed;
		}
}
           

在數組指定位置插入元素

Is it possible to write a version of this method that returns void and changes arr in place (i.e., destructively)?

No, because arrays have a fixed size, so to add an element, you need to create a new array.

public static int[] insert(int[] arr, int item, int position){
	int[] result =new int[arr.length +1];
	position = Math.min(arr.length,position);
	for(int i=0;i<position;i++){
		result[i] = arr[i];
		}
		result[position] = item;
		for(int i = position;i<arr.length;i++){
			result[i+1] = arr[i];
		}
			return result;
	}
			
           

在原數組上逆轉元素

What is the fewest number of iteration steps you need? What is the fewest number of additional variables you need?

Half the length of the array. You can swap the two paired indices at the same step.One additional variable as a temporary buffer during the swap; one index for the iteration. More may make your code neater.

public static void reverse(int[] arr){
	for(int i=o;i<arr.length/2;i++){
		int j = arr.length-i-1;
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
		}
	}
           

無題

: Write a non-destructive method replicate(int[] arr) that replaces the

number at index i with arr[i] copies of itself. For example, replicate([3, 2,

1]) would return [3, 3, 3, 2, 2, 1].

public static int[] replicate(int[] arr) {
	 int total = 0;
	for (int item : arr) {
	 total += item;
	}
	 int[] result = new int[total];
	 int i = 0;
	 for (int item : arr) {
	for (int counter = 0; counter < item; counter++) {
	 result[i] = item;
	 i++;
	 }
 	}
	 return result;
 }