展平Java中的链接列表

debugcn 发表于 Dev

奥丁

我正在尝试展平多级链接列表。给定一个链表，其中每个节点代表一个链表并包含两个其类型的指针：（i）指向主列表中下一个节点的指针（在下面的代码中我们称之为“正确”指针）（ii）指向链表的指针这个节点在哪里（在下面的代码中我们称其为“向下”指针）。所有链接列表已排序

   5 -> 10 -> 19 -> 28
   |    |     |     |
   V    V     V     V
   7    20    22    35
   |          |     |
   V          V     V
   8          50    40
   |                |
   V                V
   30               45

到

5 7 8 10 19 20 22 28 30 35 40 45 50

下面是我的Java代码：

public class FlattenAList {
public static MultiNode<Integer> end = new MultiNode<Integer>(0);
public static MultiNode<Integer> result = end;

public static MultiNode flatten(MultiNode head) {
    if (head == null || head.right == null)
        return head;
    MultiNode<Integer> tmp = head;

    while (tmp != null) {
        merge(tmp, result);
        tmp = tmp.right;
    }
    return result;
}

public static void merge(MultiNode<Integer> a, MultiNode<Integer> b) {
    if (a == null) {
        end.down = b;
        end = end.down;
        return;
    }
    if (b == null) {
        end.down = a;
        end = end.down;
        return;
    }

    if (a.data <= b.data) {
        end.down = a;
        end = end.down;
        merge(a.down, b);
    } else {
        end.down = b;
        end = end.down;
        merge(a, b.down);
    }
}
}

该合并函数是有问题的，我得到java.lang.StackOverflowError的在java.lang.Integer.intValue（来源不明）

在if（a.data <= b.data）

MChaker

这是一种根据您的需要快速简便的方法。

package example;

public class FlattenAList {

    private static MultiNode<Integer> merge(MultiNode<Integer> a, MultiNode<Integer> b) {
        MultiNode<Integer> head = new MultiNode<Integer>();
        MultiNode<Integer> temp = head;
        while (a != null && b != null) {
            if (a.data < b.data) {
                temp.down = a;
                temp = temp.down;
                a = a.down;
            } else if (b.data < a.data) {
                temp.down = b;
                temp = temp.down;
                b = b.down;
            }
        }

        temp.down = (a == null) ? b : a;
        return head.down;
    }

    static class MultiNode<T> {
        T data;
        MultiNode<T> right;
        MultiNode<T> down;

        public MultiNode(T data) {
            this.data = data;
        }

        public MultiNode() {

        }
    }

    public static MultiNode<Integer> flatten(MultiNode<Integer> root) {

        MultiNode<Integer> temp = root;
        MultiNode<Integer> result = null;
        while (temp != null) {
            result = merge(temp, result);
            temp = temp.right;
        }
        return result;
    }

    public static void print(MultiNode<Integer> start) {
        while (start != null) {
            System.out.print(start.data+" ");
            start = start.down;
        }
    }

    public static void main(String[] args) {
        MultiNode<Integer> start = new MultiNode<Integer>(5);
        start.right = new MultiNode<Integer>(10);
        start.right.right = new MultiNode<Integer>(19);
        start.right.right.right = new MultiNode<Integer>(28);

        start.down = new MultiNode<Integer>(7);
        start.down.down = new MultiNode<Integer>(8);
        start.down.down.down = new MultiNode<Integer>(30);

        start.right.down = new MultiNode<Integer>(20);

        start.right.right.down = new MultiNode<Integer>(22);
        start.right.right.down.down = new MultiNode<Integer>(50);

        start.right.right.right.down = new MultiNode<Integer>(35);
        start.right.right.right.down.down = new MultiNode<Integer>(40);
        start.right.right.right.down.down.down = new MultiNode<Integer>(45);
        // Node result = flatten(start);
        MultiNode<Integer> result = flatten(start);
        print(result);
    }
}

输出：