CS61B Lab2

IntList 介绍

IntList 是一个简单的递归链表，用于存储整数。每个节点包含两个字段：
- first: 当前节点的整数值。
- rest: 指向下一个IntList节点的引用（可能是另一个IntList）。

破坏性方法（如 dSquareList）：直接修改原链表的内容。

非破坏性方法（如 squareListIterative）：创建一个新链表，保留原链表不变。

方法概述

在IntList类中，我们需要实现以下方法：

dSquareList(IntList L):

功能：对链表中的每个元素进行“破坏性”平方操作（直接修改原链表）。

实现：

public static void dSquareList(IntList L) {
    while (L != null) {
        L.first = L.first * L.first; // 将当前节点的值平方
        L = L.rest; // 移动到下一个节点
    }
}

squareListIterative(IntList L):

功能：返回一个新的链表，包含原链表所有元素的平方（不修改原链表）。

实现：

public static IntList squareListIterative(IntList L) {
    if (L == null) {
        return null; // 如果原链表为空，返回null
    }
    IntList result = new IntList(L.first * L.first, null); // 创建新的结果链表并平方第一个元素
    IntList current = result; // 当前指针指向结果链表
    L = L.rest; // 移动到原链表的下一个节点
    
    while (L != null) {
        current.rest = new IntList(L.first * L.first, null); // 添加平方后的元素
        current = current.rest; // 移动当前指针
        L = L.rest; // 移动到原链表的下一个节点
    }
    return result; // 返回新的结果链表
}

squareListRecursive(IntList L):

功能：返回一个新的链表，包含原链表所有元素的平方（不修改原链表）。

实现：

public static IntList squareListRecursive(IntList L) {
    if (L == null) {
        return null; // 如果原链表为空，返回null
    }
    // 创建新的节点，平方当前节点的值，并递归处理下一个节点
    return new IntList(L.first * L.first, squareListRecursive(L.rest));
}

dcatenate(IntList A, IntList B):

功能：将链表A和B连接在一起，可能会修改A（破坏性）。

实现：

public static IntList dcatenate(IntList A, IntList B) {
    if (A == null) {
        return B; // 如果A为空，返回B
    }
    IntList current = A;
    while (current.rest != null) {
        current = current.rest; // 遍历到A的最后一个节点
    }
    current.rest = B; // 将B连接到A的末尾
    return A; // 返回修改后的A
}

catenate(IntList A, IntList B):

功能：将链表A和B连接在一起，不修改A（非破坏性）。

实现：

public static IntList catenate(IntList A, IntList B) {
    if (A == null) {
        return B; // 如果A为空，返回B
    }
    IntList result = new IntList(A.first, null); // 创建新的结果链表
    IntList current = result; // 当前指针指向结果链表
    IntList temp = A.rest; // 用于遍历A的其余部分

    while (temp != null) {
        current.rest = new IntList(temp.first, null); // 添加A的剩余元素
        current = current.rest; // 移动当前指针
        temp = temp.rest; // 移动到A的下一个节点
    }

    current.rest = B; // 将B连接到结果链表的末尾
    return result; // 返回新创建的链表
}

以上实现了IntList类中的所有必要方法，包括破坏性和非破坏性操作。

破坏性方法（如dSquareList和dcatenate）直接修改原链表，而非破坏性方法（如squareListIterative、squareListRecursive和catenate）则创建新的链表。

在实现过程中，应注意指针的管理，确保不会发生内存泄漏或错误连接。通过合理的边界条件检查（如对空链表的处理），可以确保代码的健壮性。