Java如何查找LinkedList中最接近目标值的节点？

这个问题我之前也碰到过，核心问题在于你只关注了目标值之前的元素，没考虑到有序链表中第一个大于目标值的元素可能离目标更近（比如目标是150，链表中有148和151，151的差是1，比148的差2更小）。下面给你几个从简单到高效的解决方案：

方案1：遍历整个链表（简单直观） #

因为链表已经排序，我们可以直接遍历每个元素，维护一个记录“当前最接近值”的变量，每次比较更新它。这种方法代码简洁，适合数据量不大的场景：

import java.util.LinkedList;
import java.util.Collections;

public class NearestNumberFinder {
    public static void main(String[] args) {
        LinkedList<Integer> numList = new LinkedList<>();
        // 填充0-300的随机数
        for (int i = 0; i < 20; i++) {
            numList.add((int) (Math.random() * 301));
        }
        // 排序链表
        Collections.sort(numList);
        System.out.println("排序后的链表: " + numList);

        int target = 150;
        Integer nearest = findNearest(numList, target);
        System.out.println("最接近 " + target + " 的数是: " + nearest);
    }

    public static Integer findNearest(LinkedList<Integer> sortedList, int target) {
        if (sortedList.isEmpty()) {
            return null; // 处理空链表的边界情况
        }

        Integer nearest = sortedList.getFirst();
        for (Integer num : sortedList) {
            int currentDiff = Math.abs(num - target);
            int nearestDiff = Math.abs(nearest - target);
            
            // 如果当前数离目标更近，更新nearest
            if (currentDiff < nearestDiff) {
                nearest = num;
            } 
            // 处理距离相等的情况（可选，比如返回较大的数）
            else if (currentDiff == nearestDiff) {
                nearest = Math.max(nearest, num);
            }
        }
        return nearest;
    }
}

代码说明： #

• 先处理空链表的边界情况，避免空指针异常
• 初始化nearest为链表第一个元素
• 遍历每个元素，计算当前元素与目标的绝对差，和当前nearest的差比较，更新nearest
• 可选处理距离相等的场景，比如返回较大的数（你也可以根据需求改成返回较小的）

方案2：利用有序特性优化遍历（提前终止） #

因为链表是有序的，当遍历到第一个大于目标值的元素时，后面的元素只会更大，与目标的差也只会越来越大，所以可以提前终止遍历，提升效率：

public static Integer findNearestOptimized(LinkedList<Integer> sortedList, int target) {
    if (sortedList.isEmpty()) {
        return null;
    }

    Integer nearest = sortedList.getFirst();
    int minDiff = Math.abs(nearest - target);

    for (Integer num : sortedList) {
        int currentDiff = Math.abs(num - target);
        if (currentDiff < minDiff) {
            minDiff = currentDiff;
            nearest = num;
            // 找到完全匹配的目标值，直接返回
            if (minDiff == 0) {
                return nearest;
            }
        }

        // 遇到第一个大于目标的元素，后面的元素差只会更大，提前终止
        if (num > target) {
            break;
        }
    }

    // 检查第一个大于目标的元素是否比当前nearest更接近
    int insertionIndex = sortedList.indexOf(nearest) + 1;
    if (insertionIndex < sortedList.size()) {
        Integer nextNum = sortedList.get(insertionIndex);
        if (Math.abs(nextNum - target) < minDiff) {
            nearest = nextNum;
        }
    }

    return nearest;
}

方案3：二分查找（高效，适合大数据量） #

如果链表数据量很大，遍历的O(n)效率不够，可以用二分查找快速定位目标值的插入位置，然后比较插入位置前后的元素，时间复杂度是O(log n)：

public static Integer findNearestWithBinarySearch(LinkedList<Integer> sortedList, int target) {
    if (sortedList.isEmpty()) {
        return null;
    }

    // 用Collections的二分查找方法，找到目标的位置
    int index = Collections.binarySearch(sortedList, target);
    if (index >= 0) {
        return sortedList.get(index); // 找到目标值，直接返回
    }

    // 没找到的话，返回值是 -(插入点) -1，插入点是第一个大于目标的元素位置
    int insertionPoint = -(index + 1);

    // 获取两个候选元素：最后一个小于目标的，和第一个大于目标的
    Integer candidateBefore = insertionPoint > 0 ? sortedList.get(insertionPoint - 1) : null;
    Integer candidateAfter = insertionPoint < sortedList.size() ? sortedList.get(insertionPoint) : null;

    // 处理边界情况（目标比所有元素小或大）
    if (candidateBefore == null) {
        return candidateAfter;
    }
    if (candidateAfter == null) {
        return candidateBefore;
    }

    // 比较两个候选元素的距离
    int diffBefore = Math.abs(candidateBefore - target);
    int diffAfter = Math.abs(candidateAfter - target);
    if (diffBefore < diffAfter) {
        return candidateBefore;
    } else if (diffAfter < diffBefore) {
        return candidateAfter;
    } else {
        // 距离相等时，返回较大的数（可按需调整）
        return Math.max(candidateBefore, candidateAfter);
    }
}

代码说明： #

• Collections.binarySearch会返回目标值的索引，如果没找到则返回-(插入点)-1，插入点就是第一个大于目标值的元素位置
• 比较插入点前后的元素，哪个离目标更近就返回哪个
• 处理了目标比所有元素都小或都大的边界情况

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