算法與資料結構基礎課第二節筆記

一些基礎資料結構，連結清單，棧，隊列

1、反轉連結清單

單連結清單

反轉單連結清單

public static Node reverseLinkedList(Node head) {
    Node pre = null;
    Node next = null;
    while (head != null) {
	next = head.next;
	head.next = pre;
	pre = head;
	head = next;
    }
    return pre;
}

// 遞歸解法
public ListNode reverseList(ListNode head) {
        if (head == null){
            return head;
        }
        ListNode cur = reverse(head,head.next);
        head.next = null;
        return cur;
}
public ListNode reverse(ListNode head, ListNode next){
        if (next==null){
            return head;
        }
        ListNode temp = reverse(head.next,next.next);
        next.next = head;
        return temp;
    }
           

 雙向連結清單

public static DoubleNode reverseDoubleList(DoubleNode head) {
	DoubleNode pre = null;
	DoubleNode next = null;
	while (head != null) {
	  next = head.next;
	  head.next = pre;
	  head.last = next;
	  pre = head;
          head = next;
	}
	return pre;
}
           

2、删除連結清單中指定的值

删除連結清單中指定的值

public Node removeValue(Head head, int num){
   while(head != null){
      if (head.value != num){
         break;
      }
      head = head.next;
   }
   Node pre = head;
   Node cur = head;
   while (cur != null){
      if (cur.value == num){
         pre.next = cur.next;
      }else{
         pre = cur;
      }
      cur = cur.next;
   }
   return head;
}
           

遞歸

例子

求數組arr[L..R]中的最大值，怎麼用遞歸方法實作

1）将[L..R]範圍分成左右兩半。左:[L..Mid] 右 [Mid + 1.. R]

2) 左部分求最大值，右部分求最大值

3）[L..R]範圍上的最大值，是max{左部分最大值，右部分最大值}

注意：2）是個遞歸過程，當範圍上隻有一個數，就可以不用再遞歸了

// 求arr中的最大值
public static int getMax(int[] arr) {
	return process(arr, 0, arr.length - 1);
}

// arr[L..R]範圍上求最大值  L ... R   N
public static int process(int[] arr, int L, int R) {
	if (L == R) { // arr[L..R]範圍上隻有一個數，直接傳回，base case
		return arr[L];
	}
	int mid = L + ((R - L) >> 1); // 中點   	1
	int leftMax = process(arr, L, mid);
	int rightMax = process(arr, mid + 1, R);
	return Math.max(leftMax, rightMax);
}