CS61B 课程笔记（DISC 03 Linked Lists, Arrays）

1. 链表操作

问题 1.1：如何在链表的特定位置插入一个元素？

解答：我们可以遍历链表直到指定的位置，并在那个位置插入一个新节点。如果链表为空，或者位置是 0，则直接在头部插入。

public void insert(int item, int position) {
  // 如果链表为空，或者插入的位置是第一个节点
  if (first == null || position == 0) {
    addFirst(item);  // 调用 addFirst 方法在头部插入
    return;  // 提前返回
  }
  // 遍历链表，寻找插入位置
  IntNode p = first;
  while (p.next != null && position != 0) {
    position--;  // 减少位置计数
    p = p.next;  // 向下一个节点移动
  }
  // 创建新节点并将其插入链表
  IntNode newNode = new IntNode(item, p.next);
  p.next = newNode;  // 将当前节点的 next 指向新节点
}

解释：我们首先检查是否需要在头部插入。如果不需要，就遍历链表到达插入位置，创建新节点并插入到链表中。

问题 1.2：如何反转链表？

解答：反转链表的过程是将链表中的指针反转，使所有节点的 next 指针指向它的前一个节点。

public void reverse() {
  IntNode currentNode = null;  // 保存反转后链表的头节点
  IntNode nextNode = first;  // 当前遍历的节点
  while (nextNode != null) {
    IntNode nextNextNode = nextNode.next;  // 暂存下一个节点
    nextNode.next = currentNode;  // 当前节点的 next 指针指向前一个节点
    currentNode = nextNode;  // 当前节点变为反转后的新头
    nextNode = nextNextNode;  // 移动到下一个节点
  }
  first = currentNode;  // 更新链表的头节点
}

解释：我们从链表的头节点开始，逐个反转每个节点的 next 指针，直到遍历完整个链表。最后，将反转后的头节点设置为 first。

问题 1.3：如何通过递归反转链表？

解答：递归实现反转链表是通过不断调用反转函数直到链表末尾，逐层回溯来反转节点的指针。

public void reverse() {
  first = reverse(first);  // 递归调用反转链表
}

private IntNode reverse(IntNode front) {
  // 如果链表为空，或者只剩下一个节点，返回该节点
  if (front == null || front.next == null) {
    return front;
  } else {
    // 递归反转后面的节点
    IntNode lastNode = reverse(front.next);
    front.next.next = front;  // 反转当前节点的指针
    front.next = null;  // 当前节点成为最后一个节点
    return lastNode;  // 返回反转后的新头节点
  }
}

解释：递归通过不断缩小问题规模来反转链表，直到链表末尾。回溯过程中，逐步反转每个节点的指针。

2. 数组操作

问题 2.1：如何在数组的特定位置插入一个元素？

解答：通过创建一个新数组，将原数组的元素分为两部分：插入位置之前的元素和之后的元素，并将新元素插入到指定位置。

public static int[] insert(int[] arr, int item, int position) {
  int[] newArr = new int[arr.length + 1];  // 创建一个新数组，长度比原数组大1
  position = Math.min(arr.length, position);  // 确保插入位置合法
  // 复制插入位置之前的元素
  for (int i = 0; i < position; i++) {
    newArr[i] = arr[i];
  }
  newArr[position] = item;  // 插入新元素
  // 复制插入位置之后的元素
  for (int i = position; i < arr.length; i++) {
    newArr[i + 1] = arr[i];
  }
  return newArr;  // 返回新数组
}

解释：我们首先计算合法的插入位置，之后将原数组的前半部分复制到新数组，再插入新元素，最后复制后半部分。

问题 2.2：如何反转一个数组？

解答：通过交换数组两端的元素，将数组反转。

public static void reverse(int[] arr) {
  int temp;  // 用于交换元素的临时变量
  for (int left = 0, int right = arr.length - 1; left < right; left++, right--) {
    temp = arr[left];  // 暂存左边的元素
    arr[left] = arr[right];  // 右边的元素赋值给左边
    arr[right] = temp;  // 左边的元素赋值给右边
  }
}

解释：我们使用两个指针，分别从数组的两端开始，逐个交换对应位置的元素，直到两个指针相遇。

问题 2.3：如何复制数组中的元素，使每个元素重复它的值对应的次数？

解答：首先计算出结果数组的大小，然后根据每个元素的值，重复该元素多次并存入新数组。

public static int[] replicate(int[] arr) {
  int size = 0;  // 计算结果数组的大小
  for (int item : arr) {
    size += item;  // 累加每个元素的值，得到总长度
  }

  int[] result = new int[size];  // 创建新数组，大小为累加后的总长度
  int i = 0;
  for (int item : arr) {
    // 按照元素的值进行多次重复
    for (int count = 0; count < item; count++) {
      result[i++] = item;
    }
  }
  
  return result;  // 返回重复后的数组
}