排序链表算法的并集

Question

这是我已经完成的第一部分：

设A和B是排序数组，其中A的所有元素都不同，B的所有元素也不同（尽管元素可以同时出现在A和B中）。设计一个O（n）算法，生成一个包含a和B的所有元素的排序数组C，而不重复。例如，如果A＝[1，2，5，7]并且B＝[2，5，10]，则C＝[1，2,5，7，10]。

但我被这个与列表有关的部分卡住了：

对于A和B是链表的情况，求解相同的练习。

我的代码：

    Merge(A,B,C)
     i=0;
     j=0;
     k=0;
     while (i < A.length && j < B.length)
          if (A.content <= B.content)
               C.content = A.content
               k = k + 1; i = i + 1

Answer 1

您的算法是不完整的：它没有告诉A.content > B.content时该做什么。该方法与众所周知的合并两个排序集合的算法几乎相同，只是当两个项目相等时，您可以推进两个集合。

使用链表不会更改算法，因为在这两种情况下，您都会对每个集合中的单个"head"元素进行操作。

merge-lists(list a, list b) -> list c
    while !a.at-end && !b.at-end
        if a.head < b.head
            c.add( a.head )
            a.move-next
        else if a.head > b.head
            c.add( b.head )
            b.move-next
        else // it means that a.head == b.head
            c.add( a.head )
            a.move-next
            b.move-next
        end
    while !a.at-end
        c.add( a.head )
        a.move-next
    while !b.at-end
        c.add( b.head )
        b.move-next