自定义LinkedList打印异常及硬币找零最优解实现问题

• 打印输出内存地址：自定义LinkedList未正确重写toString()方法，直接打印对象时默认调用Object类的toString()，返回类名@哈希值格式的地址字符串。之前尝试编写的toString()存在逻辑错误：遍历起点设为head.next，跳过了头节点存储的首枚硬币，空链表场景还会触发空指针。
• 存储的子链表全部失效：回溯过程中直接将同一个ll实例的引用存入ll_total，后续回溯修改ll内容时，之前存入的所有条目会同步被篡改，最终存储的全是被回溯操作打乱的无效对象，无法拿到正确组合。
• 无法筛选最优解：缺少链表长度统计能力，无法对比不同组合的硬币数量。
• 原有回溯逻辑存在缺陷：插入子链表的时机错误，删除节点时固定删0号位置打乱了组合顺序，全局counter变量的计数逻辑不可靠。

1. Node类 #

保持原有结构无需额外修改：

public class Node {
    int data;
    LinkedList ll;
    Node next;
}

2. LinkedList类修改 #

补全正确的toString()、长度统计、链表快照复制、最优解筛选方法，修复遍历和删除的空指针问题：

public class LinkedList {
    Node head;

    // 插入硬币值
    public void insert(int data) {
        Node node = new Node();
        node.data = data;
        node.next = null;
        if (head == null) {
            head = node;
        } else {
            Node n = head;
            while(n.next != null) {
                n = n.next;
            }
            n.next = node;
        }
    }

    // 存入子链表快照
    public void insert_ll(LinkedList ll) {
        Node node = new Node();
        node.ll = ll;
        node.next = null;
        if (head == null) {
            head = node;
        } else {
            Node n = head;
            while(n.next != null) {
                n = n.next;
            }
            n.next = node;
        }
    }

    public void deleteAt(int index) {
        if (head == null) return;
        if(index == 0) {
            head = head.next;
        } else {
            Node n = head;
            for (int i = 0; i < index - 1; i++) {
                n = n.next;
                if (n == null) return;
            }
            if (n.next == null) return;
            Node n1 = n.next;
            n.next = n1.next;
            n1 = null;
        }
    }

    // 正确重写toString，格式化输出硬币组合
    @Override
    public String toString() {
        if (head == null) {
            return "[]";
        }
        StringBuilder sb = new StringBuilder("[");
        Node n = head;
        while (n != null) {
            sb.append(n.data);
            if (n.next != null) {
                sb.append(", ");
            }
            n = n.next;
        }
        sb.append("]");
        return sb.toString();
    }

    // 获取链表长度（即当前组合的硬币总数）
    public int size() {
        int count = 0;
        Node n = head;
        while (n != null) {
            count++;
            n = n.next;
        }
        return count;
    }

    // 复制当前链表生成独立快照，避免回溯修改引用对象
    public LinkedList copy() {
        LinkedList newLl = new LinkedList();
        Node n = head;
        while (n != null) {
            newLl.insert(n.data);
            n = n.next;
        }
        return newLl;
    }

    // 打印所有存储的子链表组合
    public void show_ll() {
        if (head == null) {
            System.out.println("没有找到有效组合");
            return;
        }
        Node node = head;
        int index = 1;
        while(node != null) {
            System.out.println("组合" + index + "：" + node.ll + "，硬币数：" + node.ll.size());
            node = node.next;
            index++;
        }
    }

    // 筛选硬币数最少的最优组合
    public LinkedList getShortest() {
        if (head == null) return null;
        LinkedList minLl = head.ll;
        int minSize = minLl.size();
        Node node = head.next;
        while (node != null) {
            int currSize = node.ll.size();
            if (currSize < minSize) {
                minSize = currSize;
                minLl = node.ll;
            }
            node = node.next;
        }
        return minLl;
    }
}

3. 主类回溯逻辑修改 #

移除不可靠的全局counter和全局ll变量，调整递归终止条件，仅在找到有效组合（剩余金额为0）时存入独立的链表快照，回溯时删除最后插入的节点保证状态正确：

import java.util.Scanner;

public class CoinChange_Backtracking {
        
    static int[] coins = {3, 2, 1};
    static LinkedList ll_total = new LinkedList();
    
    
    public static void main(String[] args) {
        Scanner myInput = new Scanner(System.in);
        int amount;
        System.out.println("Put in the amount of money: ");
        amount = myInput.nextInt();
        if (amount < 101) {
            LinkedList initialLl = new LinkedList();
            recursiveFunction(coins, amount, 0, initialLl);
            System.out.println("所有有效找零组合：");
            ll_total.show_ll();
            LinkedList best = ll_total.getShortest();
            System.out.println("\n最优找零组合（硬币数最少）：" + best + "，共" + best.size() + "枚硬币");
        } else {
            System.out.println("The value must be less than 100!");
        }
    }

    
    public static void recursiveFunction(int[] coins, int amount, int index_coins, LinkedList ll) {
        // 找到有效组合，复制快照存入总链表
        if (amount == 0) {
            ll_total.insert_ll(ll.copy());
            return;
        }
        // 硬币遍历完直接返回
        if (index_coins >= coins.length) {
            return;
        }
        // 选择当前硬币（面值不超过剩余金额时可选）
        if (coins[index_coins] <= amount) {
            ll.insert(coins[index_coins]);
            recursiveFunction(coins, amount - coins[index_coins], index_coins, ll);
            // 回溯，撤销选择
            ll.deleteAt(ll.size() - 1);
        }
        // 不选当前硬币，遍历下一个面值
        recursiveFunction(coins, amount, index_coins + 1, ll);
    }
}

输入目标金额后，首先输出所有合法的找零组合，直接展示硬币面值和对应硬币数量，不会再出现内存地址格式的输出。所有组合遍历完成后，自动筛选出节点数最少的链表，输出硬币总数最少的最优找零方案。

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