How to Merge Two List/Iterators in Java?

  • 时间：2020-09-09 14:04:20
  • 分类：网络文摘
  • 阅读：110 次

We have known the approach to merge two linked list in C++. We also know how to apply the merge sort algorithms to merge K sorted list. If you are given two Iterators in Java, how are you supposed to merge them into one list if both iterators are sorted?

The Java’s iterator has two important methods you can use: hasNext() and next(). The hasNext() returns a boolean telling if this iterator reaches the end. And the next() will advance to next position and returns the value of it. It will throw exception if the iterator is beyond the end (EOF).

Merging Two Sorted Iterators in Java

Remember, everytime we call next() we have to put a safety check hasNext(). Then the logic is pretty simple: we first deal with the merging when both iterators are not NULL.

Then, we have to follow the remaining iterator and copy over the values.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

package helloacm.com
import lombok.var;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;
 
public class Main {
    public static List<Integer> merge(Iterator<Integer> it1, Iterator<Integer> it2) {
        List<Integer> res = new ArrayList<>();
        var v1 = it1.hasNext() ? it1.next() : null;
        var v2 = it2.hasNext() ? it2.next() : null;
        while (v1 != null && v2 != null) {
            if (v1 < v2) { // pick the smaller one
                res.add(v1);
                v1 = it1.hasNext() ? it1.next() : null;
            } else {
                res.add(v2);
                v2 = it2.hasNext() ? it2.next() : null;
            }
        }
        while (v1 != null) {
            res.add(v1);
            v1 = it1.hasNext() ? it1.next() : null;
        }
        while (v2 != null) {
            res.add(v2);
            v2 = it2.hasNext() ? it2.next() : null;
        }
        return res;
    }
 
    public static void main(String[] args) {
        var l1 = Arrays.asList(1, 3, 5, 7, 9, 11, 15, 17);
        var l2 = Arrays.asList(2, 4, 6, 8, 10, 12, 16, 18);
        var sorted = merge(l1.iterator(), l2.iterator());
        for (var num: sorted) {
            System.out.println(num);
        }
    }
}
package helloacm.com
import lombok.var;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;

public class Main {
    public static List<Integer> merge(Iterator<Integer> it1, Iterator<Integer> it2) {
        List<Integer> res = new ArrayList<>();
        var v1 = it1.hasNext() ? it1.next() : null;
        var v2 = it2.hasNext() ? it2.next() : null;
        while (v1 != null && v2 != null) {
            if (v1 < v2) { // pick the smaller one
                res.add(v1);
                v1 = it1.hasNext() ? it1.next() : null;
            } else {
                res.add(v2);
                v2 = it2.hasNext() ? it2.next() : null;
            }
        }
        while (v1 != null) {
            res.add(v1);
            v1 = it1.hasNext() ? it1.next() : null;
        }
        while (v2 != null) {
            res.add(v2);
            v2 = it2.hasNext() ? it2.next() : null;
        }
        return res;
    }

    public static void main(String[] args) {
        var l1 = Arrays.asList(1, 3, 5, 7, 9, 11, 15, 17);
        var l2 = Arrays.asList(2, 4, 6, 8, 10, 12, 16, 18);
        var sorted = merge(l1.iterator(), l2.iterator());
        for (var num: sorted) {
            System.out.println(num);
        }
    }
}

Unlike linked lists, for iterators, you have to iterate and copy over the values. With linked list, you can just re-point/re-connect the head with O(1) constant time.

The runtime complexity is O(M+N) where M and N are the number of the elements in each iterator respectively. The space requirement is also O(M+N).

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读：
内蒙古卫视直播-内蒙古卫视在线直播观看「高清」　 重庆卫视直播-重庆卫视在线直播观看「高清」　 广东卫视直播-广东卫视在线直播观看「高清」　 深圳卫视直播-深圳卫视在线直播观看「高清」　 四川卫视直播-四川卫视在线直播观看「高清」　 厦门卫视直播-厦门卫视在线直播观看「高清」　 广西卫视直播-广西卫视在线直播观看「高清」　 东南卫视直播-东南卫视在线直播观看「高清」　 陕西卫视直播-陕西卫视在线直播观看「高清」　 农林卫视直播-陕西农林卫视在线直播观看「高清」　
评论列表
添加评论