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:
- no duplicated value exists in the cyclic linked list
- one and only one cyclic linked list can be rebuilt from the array of linked lists' head nodes
- every node can be returned as the entrance to the cyclic linked list
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;
}
}
CodePudding user response：
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
CodePudding user response：
Use a HashMap to keep track of which value follows after another. This way you will find all links except maybe one. By keeping track of the values for which you don't know yet a predecessor (which becomes smaller as you process the lists), you'll end up with one such value, which can be used to make the cycle.
I would also simplify some initialisation code, by defining some constructors for 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);
}
}