A cyclic linked list is described by several acyclic linked lists. Restore the cyclic linked list from them.
This question can be also described as:
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.
Assume that:
It's pretty hard to describe the question in words. See examples below.
Example 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
Example 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.
Example 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.
My code below seems to work, but definitely with low efficiency. I wondering whether there is a more elegent way to do this.
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;
}
}
You could maintain a vector of parent pointers or next pointers that specifies which element is the parent (or next element) of a given element. For example, when parsing the input L=[[0,1,2],...], set next[0]=1. The vector next might not have consecutive indices, and in Python, dictionaries are convenient for this purpose because the indices do not have to be consecutive integers. For example, in the code below, L does not contain the element 8. Here's code in 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))
Output:
[1, 2, 0, 6, 7, 9, 10, 3, 4, 5], where the next element of 5 is 1