CS61B 课程笔记（Examprep03 Linked Lists, Arrays）

1. 扁平化二维数组

代码片段 1：将二维数组转换为一维数组

public static int[] flatten(int [][] x) {
  int totalLength = 0;  // 用于存储二维数组的总元素数量

  // 计算二维数组中的所有元素数量
  for (int i = 0; i < x.length; i++) {
    totalLength += x[i].length;
  }

  int[] a = new int[totalLength];  // 创建一维数组用于存储结果
  int aIndex = 0;  // 一维数组的索引

  // 遍历二维数组，将每个元素按顺序放入一维数组
  for (int i = 0; i < x.length; i++) {
    for (int j = 0; j < x[i].length; j++) {
      a[aIndex] = x[i][j];
      aIndex++;  // 更新一维数组的索引
    }
  }

  return a;  // 返回一维数组
}

解释：
这个方法用于将一个二维数组 x 转换为一个一维数组。首先，计算二维数组中所有元素的总数量。然后创建一个对应大小的一维数组，最后将二维数组中的每个元素按顺序复制到新的一维数组中。

2. 跳步链表 (Skippify)

代码片段 2：链表中的跳步操作

public class IntList {
  public int first;  // 链表当前节点的值
  public IntList rest;  // 指向下一个节点的引用
  
  @Override
  public boolean equals(Object o) {...}  // 重写 equals 方法
  public static IntList list(int... args) {...}  // 创建链表的静态方法
  
  public void skippify() {
    IntList p = this;  // 从链表头开始
    int n = 1;  // 跳步计数
    while (p != null) {
      IntList next = p.rest;  // 临时保存下一个节点的引用
      for(int i = 0; i < n; i++) {  // 跳过 n 个节点
        if (next == null) {
          return;  // 如果下一个节点为 null，则结束
        }
        next = next.rest;  // 跳到下一个节点
      }
      p.rest = next;  // 跳过节点，更新当前节点的 rest
      p = p.rest;  // 移动到下一个节点
      n += 1;  // 增加跳步计数
    }
  }
}

解释：
skippify 方法在链表中跳过一定数量的节点。初始时，跳过 1 个节点，然后增加跳步的数量，每次循环跳过更多的节点，直到链表末尾。这个方法会改变链表的结构，通过跳步使得某些节点被跳过。

3. 删除链表中的重复元素

代码片段 3：从已排序的链表中移除重复的元素

public class IntList {
  public int first;  // 链表当前节点的值
  public IntList rest;  // 指向下一个节点的引用
  public IntList(int f, IntList r) {
    this.first = f;
    this.rest = r;
  }

  /**
  * 给定一个已排序的链表，移除重复的元素。
  * 例如：给定链表 1 -> 2 -> 2 -> 2 -> 3，
  * 修改后应变成 1 -> 2 -> 3（破坏性操作）。
  */
  public static void removeDuplicates(IntList p) {
    if (p == null) {
      return;  // 如果链表为空，直接返回
    }

    IntList current = p.rest;  // 当前节点
    IntList previous = p;  // 前一个节点

    // 遍历链表，直到结束
    while (current != null) {
      if (current.first == previous.first) {
        previous.rest = current.rest;  // 如果当前节点的值与前一个相同，跳过当前节点
      } else {
        previous = current;  // 否则移动到下一个节点
      }
      current = current.rest;  // 移动到下一个节点
    }
  }
}