title: How to restore a cyclic linked list from an array of head nodes of several acyclic linekd lists?
body: <p>A cyclic linked list is described by several acyclic linked lists. Restore the cyclic linked list from them.</p>
  <p>This question can be also described as:</p>
  <p>Given an array of head nodes of several acyclic linked lists. Build a cyclic linked list which exactly matches the succession relations of each nodes in the acyclic linked lists.</p>
  <p>Assume that:</p>
  <ul>
  <li>no duplicated value exists in the cyclic linked list</li>
  <li>one and only one cyclic linked list can be rebuilt from the array of linked lists' head nodes</li>
  <li>every node can be returned as the entrance to the cyclic linked list</li>
  </ul>
  <p>It's pretty hard to describe the question in words. See examples below.</p>
  <p>Example 1:</p>
  <pre><code>    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
  </code></pre>
  <p>Example 2:</p>
  <pre><code>    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.
  </code></pre>
  <p>Example 3:</p>
  <pre><code>    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.
  </code></pre>
  <p>My code below seems to work, but definitely with low efficiency. I wondering whether there is a more elegent way to do this.</p>
  <pre><code>import java.util.*;
  
  public class Test {
      public static void main(String[] args) {
          List&lt;ListNode&gt; src = new ArrayList&lt;&gt;();
          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&lt;ListNode&gt; nodes) {
          // partly restored circular list. the first element is connected to the last element
          List&lt;Integer&gt; res = new ArrayList&lt;&gt;();
          // values that have been added to res.
          Set&lt;Integer&gt; set = new HashSet&lt;&gt;();
          // 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 &amp;&amp; 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 &amp;&amp; !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 &amp;&amp; !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 -&gt; temp
                  List&lt;Integer&gt; temp2 = new ArrayList&lt;&gt;();
                  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;
      }
  
  }
  </code></pre>