一個回圈鏈表由幾個非回圈鏈表描述。從它們中恢復回圈鏈表。
這個問題也可以描述為：
給定幾個非回圈鏈表的頭節點陣列。建立一個與非回圈鏈表中每個節點的繼承關系完全匹配的回圈鏈表。
假使，假設：
- 回圈鏈表中不存在重復值
- 可以從鏈表的頭節點陣列中重建一個且只有一個回圈鏈表
- 每個節點都可以作為回圈鏈表的入口回傳
很難用語言來描述這個問題。請參閱下面的示例。
示例 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;
}
}
uj5u.com熱心網友回復：
您可以維護一個父指標或下一個指標的向量，指定哪個元素是給定元素的父（或下一個元素）。例如，在決議輸入 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
uj5u.com熱心網友回復：
使用 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);
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/463756.html
下一篇：大小為K的有色團的演算法