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

Question

我正在编写一个程序来计算小于 1,000,000 的 3 和 5 的倍数。我有一个函数可以在 2 个单独的链表中正确 returns 3 的倍数和 5 的倍数。现在我想将这 2 个链接列表组合成一个排序的非重复链接列表。我尝试了以下代码，但 "next" 在我的案例中不是定义的元素，因为我使用的是链接列表库。我无法承受将运行时扩展到除线性算术以外的任何东西 - 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

如果您有权访问 Java 8，那么使用流可以更有效地完成此操作：

Set<Integer> mySet= IntStream.range(0, 1000000)
    .filter(n -> n % 3 == 0 || n % 5 == 0)
    .collect(Collectors.toSet());

这比创建单独的列表然后合并要快得多。

如果您确实想合并两个列表：

Set<Integer> mySet = Streams.concat(list1.stream(), list2.stream())
    .collect(Collectors.toSet());

如果您没有 Java 8，那么也许只需将两个列表都添加到 Set。 TreeSet 是一个 SortedSet，因此您无需担心排序问题：

Set<Integer> final = new TreeSet<>();
if (list1 != null)
    final.addAll(list1);
if (list2 != null)
    final.addAll(list2);
return final;

Answer 2

Java 7 非流版本：

private static LinkedList<Integer> mergeLists(LinkedList<Integer> ll1, LinkedList<Integer> ll2) {
    TreeSet<Integer> set = new TreeSet<>();
    set.addAll(ll1);
    set.addAll(ll2);
    return new LinkedList<Integer>(set);
}

Answer 3

根据 OP 的要求，递归算法合并两个已排序的 LinkedList 并跳过重复项。这在 O(n) 中运行，其中 n 是两个列表中元素的总数。

请注意，此（递归）对于您声明的 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);
}

Answer 4

您不需要为此目的合并两个列表。将 3 和 5 插入数组中。维护三个辅助变量 1.divisible_by_five 2. divisible_by_three 和 3.max 最初，divisible_by_five = 5，divisible_by_three = 3，最大值 = 5

do{
    if(divisible_by_three+3 < divisible_by_five+5){
        divisible_by_three += 3;
        max = divisible_by_three;
    }
    else if(divisible_by_three+3 > divisible_by_five+5){
        divisible_by_five += 5;
        max = divisible_by_five;
    }
    else{
        divisible_by_3 +=3;
        max = divisible_by_five = divisible_by_3;
    }
    insertIntoList(max);
}while(max<100000);

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

how can I merge 2 sorted linked lists by only using recursion

java

sorting

merge

linked-list