如何从几个非循环linekd列表的头节点数组中恢复一个循环链表？

Question

一个循环链表由多个非循环链表描述。从他们那里恢复循环链表。

本题也可以描述为：

给定几个非循环链表的头节点数组。建立一个与非循环链表中每个节点的继承关系完全匹配的循环链表。

假设：

循环链表中不存在重复值
可以从链表的头节点数组重建一个循环链表
每个节点都可以作为循环链表的入口返回

很难用文字描述这个问题。请参阅下面的示例。

示例 1：

    Input: [[0, 1, 2], [1, 2, 3], [3, 4], [4, 0, 1]]
    Output: [0, 1, 2, 3, 4], where the next element of 4 is 0

示例 2：

    Input: [[3, 4], [0, 1], [2, 3], [1, 2], [4, 0], [0, 1, 2, 3, 4]]
    Output: [0, 1, 2, 3, 4], where the next element of 4 is 0.

示例 3：

    Input: [[1, 2, 0, 6], [2, 0, 6, 7], [7, 9], [3, 4], [7, 9, 10, 3], [4, 5, 1]] 
    Output: [3, 4, 5, 1, 2, 0, 6, 7, 9, 10], where the next element of 10 is 3.

我下面的代码似乎可以工作，但效率肯定很低。我想知道是否有更优雅的方法来做到这一点。

import java.util.*;

public class Test {
    public static void main(String[] args) {
        List<ListNode> src = new ArrayList<>();
        ListNode temp = new ListNode();
        temp.val = 1;
        temp.next = new ListNode();
        temp.next.val = 2;
        temp.next.next = new ListNode();
        temp.next.next.val = 0;
        temp.next.next.next = new ListNode();
        temp.next.next.next.val = 6;
        src.add(temp);

        temp = new ListNode();
        temp.val = 2;
        temp.next = new ListNode();
        temp.next.val = 0;
        temp.next.next = new ListNode();
        temp.next.next.val = 6;
        temp.next.next.next = new ListNode();
        temp.next.next.next.val = 7;
        src.add(temp);

        temp = new ListNode();
        temp.val = 7;
        temp.next = new ListNode();
        temp.next.val = 9;
        src.add(temp);

        temp = new ListNode();
        temp.val = 3;
        temp.next = new ListNode();
        temp.next.val = 4;
        src.add(temp);

        temp = new ListNode();
        temp.val = 7;
        temp.next = new ListNode();
        temp.next.val = 9;
        temp.next.next = new ListNode();
        temp.next.next.val = 10;
        temp.next.next.next = new ListNode();
        temp.next.next.next.val = 3;
        src.add(temp);

        temp = new ListNode();
        temp.val = 4;
        temp.next = new ListNode();
        temp.next.val = 5;
        temp.next.next = new ListNode();
        temp.next.next.val = 1;
        src.add(temp);


        ListNode res = solve(src);
        ListNode p = res.next;
        System.out.println(res.val);
        while (p != res) {
            System.out.println(p.val);
            p = p.next;
        }
    }

    static class ListNode {
        int val;
        ListNode next;
    }

    //n ^ 2 k
    static ListNode solve(List<ListNode> nodes) {
        // partly restored circular list. the first element is connected to the last element
        List<Integer> res = new ArrayList<>();
        // values that have been added to res.
        Set<Integer> set = new HashSet<>();
        // add the first linked list to res
        ListNode head = nodes.get(0);
        while (head != null) {
            res.add(head.val);
            set.add(head.val);
            head = head.next;
        }
        // remove the first linked list from unvisited linked lists, because all of its nodes have been added to res
        nodes.remove(0);
        // visit the ith linked list of nodes in the following loop
        int i = 0;
        // while there is still linked list that hasn't been visited.
        while (!nodes.isEmpty()) {
            ListNode p = nodes.get(i);
            // there is overlap between res and the linked list we are visiting
            if (set.contains(p.val)) {
                // find the first element that hasn't been added to res.
                p = p.next;
                while (p != null && set.contains(p.val)) {
                    p = p.next;
                }
                // since no duplicated value exists, position of the unoverlaped section, which starts at p and ends at unknowns, can be added to the tail of res, the circular linked list.
                while (p != null && !set.contains(p.val)) {
                    res.add(p.val);
                    set.add(p.val);
                    p = p.next;
                }
            } else { // maybe there is overlap, or maybe not. we don't know yet.
                // overlap may occurs later in the linked list we are visiting. find it out
                ListNode temp = p;
                while (temp != null && !set.contains(temp.val)) {
                    temp = temp.next;
                }
                // no overlap. So the position of the linked list cannot be determined. continue to visit the next linked list.
                if (temp == null) {
                    i++;
                    continue;
                }
                // there is overlap from temp to end. But there is no overlap from p to temp - 1.
                // So, we can know that the section that starts at p and ends at temp - 1 is in front of res. So, add res to it
                // it seems redundant here? I can add the section to res since it's a circular list
                //p -> temp
                List<Integer> temp2 = new ArrayList<>();
                while (p != temp) {
                    temp2.add(p.val);
                    set.add(p.val);
                    p = p.next;
                }
                temp2.addAll(res);
                res = temp2;
            }
            // ith linked list has been visited and all of its nodes have been added to res. remove it from unvisited list and try to visit all linked lists again.
            nodes.remove(i);
            i = 0;
        }
        // construct circular linked list to return
        ListNode dummyHead = new ListNode();
        ListNode p = dummyHead;
        for (int val : res) {
            p.next = new ListNode();
            p.next.val = val;
            p = p.next;
        }
        p.next = dummyHead.next;
        return dummyHead.next;
    }

}

Answer 1

您可以维护一个父指针或下一个指针的向量，指定哪个元素是给定元素的父元素（或下一个元素）。例如，在解析输入 L=[[0,1,2],...] 时，设置 next[0]=1。向量 next 可能没有连续的索引，在 Python 中，字典很方便用于此目的，因为索引不必是连续的整数。例如，在下面的代码中，L 不包含元素 8。这里是 Python 中的代码：

L = [[1, 2, 0, 6], [2, 0, 6, 7], [7, 9], [3, 4], [7, 9, 10, 3], [4, 5, 1]] 
    
next = {}
for cycle in L:
    m = len(cycle)
    for i in range(m-1):  #for i=0,1,...,m-2
        #make cycle[i+1] the next value of cycle[i]
        next[cycle[i]] = cycle[i+1]

#print res = [i, next[i], next[next[i]]...]
i = list(next.keys())[0]
res = [i]
y = next[i]
while y!= i:
    res.append(y)
    x = y
    y = next[y]
print(str(res) + ", where the next element of " +  str(x) +  " is " + str(i))

输出：

[1, 2, 0, 6, 7, 9, 10, 3, 4, 5], where the next element of 5 is 1

Answer 2

使用 HashMap 来跟踪一个接一个的值。这样你会找到所有链接，也许只有一个链接除外。通过跟踪您还不知道前任的值（随着您处理列表而变得更小），您最终会得到一个这样的值，它可以用来进行循环。

我还会通过为 ListNode:

定义一些构造函数来简化一些初始化代码

    static ListNode createList(int... arr) {
        ListNode head = null;
        for (int j = arr.length - 1; j >= 0; j--) {
            head = new ListNode(arr[j], head); 
        }
        return head;
    }

    
    public static void main(String[] args) {
        List<ListNode> src = new ArrayList<>(
            Arrays.asList(
                createList(1, 2, 0, 6),
                createList(2, 0, 6, 7),
                createList(7, 9),
                createList(3, 4),
                createList(7, 9, 10, 3),
                createList(4, 5)
            )
        );

        ListNode res = solve(src);
        res.print();
    }

    static class ListNode {
        int val;
        ListNode next;

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }

        ListNode(int val) {
            this.val = val;
            this.next = null;
        }

        void print() {
            System.out.print(this.val + " ");
            ListNode node = this.next;
            while (node != this && node != null) {
                System.out.print(node.val + " ");
                node = node.next;
            }
            System.out.println();
        }
    }

    static ListNode solve(List<ListNode> nodes) {
        if (nodes.size() == 0) {
            return null;
        }
        HashMap<Integer, Integer> map = new HashMap<>();
        HashSet<Integer> roots = new HashSet<>();
        // Collect potential head values
        for (var node : nodes) {
            roots.add(node.val);
        }
        // Link every value with its successor
        for (var node : nodes) {
            while (node != null) {
                if (node.next != null) {
                    map.put(node.val, node.next.val);
                    roots.remove(node.next.val);
                } else if (!map.containsKey(node.val)) {
                    map.put(node.val, node.val); // temporary self ref
                }
                node = node.next;
            }
        }
        // Create the circular list based on the map
        ListNode head = new ListNode(nodes.get(0).val);
        ListNode node = head;
        while (true) {
            int next = map.get(node.val);
            if (next == node.val) { // Self ref: we don't know next
                for (int val : roots) { // Will only iterate once
                    next = val; // Take the value without predecessor
                }
            }
            if (next == head.val) { // Back to beginning
                node.next = head; // Make the cycle
                return head;
            }
            node = node.next = new ListNode(next);
        }
    }

如何从几个非循环linekd列表的头节点数组中恢复一个循环链表？

How to restore a cyclic linked list from an array of head nodes of several acyclic linekd lists?

algorithm

linked-list

circular-list