java - 如何仅使用递归来合并2个已排序的链表

Question

我正在编写一个程序来计算小于 1,000,000 的 3 和 5 的倍数。我有一个函数，可以在 2 个单独的链表中正确返回 3 的倍数和 5 的倍数。现在我想将这两个链表组合成一个排序的非重复链表。我尝试了以下代码，但“下一个”在我的情况下不是定义的元素，因为我使用的是链接列表库。我无法承受将运行时间炸毁至线性运算 - O(n log n) 以外的任何东西。

private static LinkedList<Integer> mergeLists(LinkedList<Integer> ll1, LinkedList<Integer> ll2) {

    LinkedList<Integer> finalList = new LinkedList();

    if (ll1 == null)
        return ll2;
    if (ll2 == null)
        return ll1;

    if (ll1.get(0) < ll2.get(0)) {
        ll1.next = MergeLists(ll1.next, ll2);
        return ll1;
    }
    else {
        ll2.next = MergeLists(ll2.next, ll1);
        return ll2;
    }
}

对于所有可能关心的人，这就是我最终所做的:

import java.util.*;

public class Multiples {

    private static LinkedList<Integer> calculate_multiples(int factor, int limit) {

        LinkedList<Integer> muls = new LinkedList<Integer>();
        boolean result_not_maxed = true;

        int counter = 1;
        while (result_not_maxed) {

            int local_result = factor*counter;
            if (local_result < limit) {

                muls.add(local_result);
                counter++;
            }
            else
                result_not_maxed = false;
        }

        return muls;
    }

    private static LinkedList<Integer> mergeLists(LinkedList<Integer> ll1, LinkedList<Integer> ll2) {

        LinkedList<Integer> finalList;
        Set<Integer> finalSet = new HashSet<>();

        finalSet.addAll(ll1);
        finalSet.addAll(ll2);

        finalList = new LinkedList<Integer>(finalSet);

        return finalList;
    }

    private static int sum(LinkedList<Integer> ll) {

        int sum = 0;
        for(int i=0; i<ll.size(); i++) {

            sum += ll.get(i);
        }

        return sum;
    }

    public static void main(String [] args) {

        LinkedList<Integer> ll_3s = Multiples.calculate_multiples(3, 1000000);
        LinkedList<Integer> ll_5s = Multiples.calculate_multiples(5, 1000000);

        LinkedList<Integer> finalList = new LinkedList<Integer>();
        finalList = Multiples.mergeLists(ll_3s, ll_5s);

        int result = sum(finalList);
        System.out.print("Sum is: " + result);
    }
}

Answer 1

根据 OP 的请求，一个递归算法合并两个排序的LinkedList并跳过重复项。运行时间复杂度为 O(n)，其中 n 是两个列表中的元素总数。

请注意，对于您所说的 100 万以内的 3 和 5 的所有倍数的用例，这种(递归)根本不切实际。

public static void main(String[] args) {
  LinkedList<Integer> list1 = Lists.newLinkedList(
      Arrays.asList(3, 6, 9, 12, 15, 18, 21, 24, 27, 30));
  LinkedList<Integer> list2 = Lists.newLinkedList(
      Arrays.asList(5, 10, 15, 20, 25, 30));

  LinkedList<Integer> combined = combine(list1, list2);
  System.out.println(combined);
}

private static LinkedList<Integer> combine(LinkedList<Integer> list1,
    LinkedList<Integer> list2) {
  LinkedList<Integer> combined = new LinkedList<>();
  combine(list1, list2, combined);
  return combined;
}

private static void combine(LinkedList<Integer> list1,
    LinkedList<Integer> list2, LinkedList<Integer> combined) {
  if (list1.size() > 0 && list2.size() > 0) {
    if (list1.peek() == list2.peek()) {
      list1.remove();
    } else if (list1.peek() < list2.peek()) {
      combined.add(list1.remove());
    } else {
      combined.add(list2.remove());
    }
  } else if (list1.size() > 0 && list2.size() == 0) {
      combined.add(list1.remove());
  } else if (list1.size() == 0 && list2.size() > 0) {
    combined.add(list2.remove());
  } else {
    return;
  }
  combine(list1, list2, combined);
}