Java自定义单链表从中间节点调用size()如何获取正确总长度

当前实现的是单向链表结构，自定义的customNode节点仅持有后继节点next的引用，没有前驱节点指针，且原有size()方法依赖链表类全局持有的头节点start从头遍历统计长度。如果仅传入一个中间节点作为遍历起点，默认只能统计该节点到尾节点的节点数量，无法访问该节点之前的链表部分，因此无法直接得到全链表的总长度。
另外注意原有size()方法中使用的Letter类属于笔误，需要替换为你定义的customNode类。

方案1：链表类维护全局长度缓存（最推荐，性能最优） #

在自定义链表的主类中新增成员变量缓存总长度，每次节点增删操作时同步更新该变量，size()方法直接返回缓存值即可，时间复杂度为O(1)，不受调用起点影响。
示例代码：

public class CustomLinkedList {
    private customNode start; // 原有的头节点引用
    private int size; // 新增全局长度缓存

    // 示例：新增节点方法同步更新size
    public void add(char letter, int score) {
        customNode newNode = new customNode(letter, score);
        if (start == null) {
            start = newNode;
        } else {
            customNode cur = start;
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = newNode;
        }
        size++; // 新增节点后长度+1
    }

    // 示例：删除节点方法同步更新size，这里省略具体删除逻辑
    public void remove(int index) {
        // 原有删除逻辑...
        size--; // 删除节点后长度-1
    }

    public int size() {
        return size; // 直接返回缓存的总长度
    }
}

方案2：修改节点为双向链表结构，新增前驱指针 #

如果确实需要支持仅通过任意节点计算全链表长度，可以修改customNode类新增前驱节点prev属性，构造节点时同步给prev赋值。拿到中间节点后先向前遍历找到头节点，再从头遍历统计总长度。
修改后的customNode示例：

public class customNode {
    public char letter;
    public int score;
    public customNode next;
    public customNode prev; // 新增前驱节点指针

    public customNode(char customNode, int score) {
        this.letter = customNode;
        this.score = score;
        this.next = null;
        this.prev = null;
    }

    public customNode(char customNode, int score, customNode next) {
        this.letter = customNode;
        this.score = score;
        this.next = next;
        this.prev = null;
        // 新增节点时如果next不为空，给next的prev赋值
        if (next != null) {
            next.prev = this;
        }
    }

    // 原有其他方法保持不变
}

对应支持任意节点调用的size()方法示例：

public int size(customNode anyNode) {
    if (anyNode == null) return 0;
    // 先向前遍历找到头节点
    customNode head = anyNode;
    while (head.prev != null) {
        head = head.prev;
    }
    // 从头遍历统计总长度
    int count = 0;
    customNode cur = head;
    while (cur != null) {
        count++;
        cur = cur.next;
    }
    return count;
}

方案3：调用时传入头节点引用（改造成本最低） #

如果不想修改现有节点和链表结构，只需要在调用size()方法时额外传入链表的头节点start，直接从头节点开始遍历统计即可，不需要调整原有类结构。
示例代码：

// 重载size方法，支持传入起始节点和头节点
public int size(customNode callNode, customNode head) {
    if (head == null) return 0;
    int count = 0;
    customNode cur = head;
    while (cur != null) {
        count++;
        cur = cur.next;
    }
    return count;
}

内容的提问来源于stack exchange，提问作者hugh