Дублируйте LinkedList с указателем на случайный node, кроме следующего node
Q: Каждый node связанного списка имеет случайный указатель (в дополнение к следующему указателю), который может случайно указывать на другой node или быть нулевым. Как бы вы дублировали такой связанный список?
A: Вот что я имею, я просто хотел ратифицировать, если это был оптимальный способ сделать это.
Поскольку нет ограничений по пространству, я буду использовать LinkedHashSet
и LinkedHashMap
(я могу представить, что люди уже кивают головой в несогласие уже;))
Первая итерация: Сделайте очевидное - прочитайте каждый node из списка, который нужно скопировать, и создайте узлы в новом списке. Затем прочитайте случайный node так: this.random.data
и вставьте в LinkedHashSet
.
Вторая итерация: перейдите в новый список и добавьте каждый node данные как первый столбец, а сам node в качестве второго столбца в LinkedHashMap
(не обязательно привязывать, но я просто идущий с потоком).
Третья итерация: Итерируйте по LinkedHashSet
(это причина, по которой это нужно связать - предсказуемое упорядочение) и новый список одновременно. Для первого node, прочитайте первую запись LinkedHashSet
, найдите соответствующий объект в LinkedHashMap
и добавьте в качестве случайного node в текущий node в новый список.
3 итерации кажутся немного сумасшедшими, но попытка заключалась в том, чтобы сохранить сложность как O (N). Любое решение, которое улучшает требования к пространству O (3N) и сложность выполнения O (3N), было бы замечательным. Спасибо!
Изменить: запись из LinkedHashSet
может быть удалена при вводе в LinkedHashMap
, поэтому это займет только пространство O (2N).
Ответы
Ответ 1
Как отмеченный MahlerFive, я думаю, что вы можете сделать это с помощью сложности O (2N) и сложностью пространства O (N).
Предположим, что у вас есть
public class Node {
private Node next;
private Node random;
private String data;
// getters and setters omitted for the sake of brevity
}
Я сделал бы глубокую копию связанного списка Node
как:
private Node deepCopy(Node original) {
// We use the following map to associate newly created instances
// of Node with the instances of Node in the original list
Map<Node, Node> map = new HashMap<Node, Node>();
// We scan the original list and for each Node x we create a new
// Node y whose data is a copy of x data, then we store the
// couple (x,y) in map using x as a key. Note that during this
// scan we set y.next and y.random to null: we'll fix them in
// the next scan
Node x = original;
while (x != null) {
Node y = new Node();
y.setData(new String(x.getData()));
y.setNext(null);
y.setRandom(null);
map.put(x, y);
x = x.getNext();
}
// Now for each Node x in the original list we have a copy y
// stored in our map. We scan again the original list and
// we set the pointers buildings the new list
x = original;
while (x != null) {
// we get the node y corresponding to x from the map
Node y = map.get(x);
// let x' = x.next; y' = map.get(x') is the new node
// corresponding to x'; so we can set y.next = y'
y.setNext(map.get(x.getNext()));
// let x'' = x.random; y'' = map.get(x'') is the new
// node corresponding to x''; so we can set y.random = y''
y.setRandom(map.get(x.getRandom()));
x = x.getNext();
}
// finally we return the head of the new list, that is the Node y
// in the map corresponding to the Node original
return map.get(original);
}
Изменить. Я обнаружил, что этот вопрос является дубликатом запроса здесь: там вы найдете , который показывает, как решить эту проблему в сложности выполнения O (3N) без лишнего пространства: очень изобретательно! Но он использует трюк с C-указателями, и я не уверен, как сделать то же самое в java.
Ответ 2
Вы можете сделать это с помощью шагов 2N и карты с N элементами.
-
Пройдите старый список, следуя указателям "next". Для каждого node, который вы посещаете, добавьте node в новый список, подключите предыдущий node в новом списке к новому node, сохраните старый node случайный указатель в новом новом node, затем сохраните сопоставление старого указателя node с новым указателем node на карте.
-
Пройдите новый список и для каждого случайного указателя найдите его на карте, чтобы найти связанный node в новом списке, чтобы заменить его.
Ответ 3
Мне тоже задали этот вопрос в интервью недавно.
Вот что я предложил.
Создайте карту исходных узлов списка, где addreess каждого node будет ключевым, и смещение случайного указателя будет значением.
Теперь создайте новый связанный список со случайным указателем = null с исходной карты.
В конце, итерация через исходный список, с помощью карты получить смещение исходного указателя и использовать это смещение, чтобы связать случайный указатель во вновь созданной карте.
В конце концов, интервьюер не был доволен. Может быть, стоит искать какой-то более подходящий подход или у него есть заданный ответ в его уме и неспособный понять новый способ его решения.
Ответ 4
Пройдите list
и используйте clone()
?
Ответ 5
в O (n) времени и с постоянным пространством
public class CloneLinkedListWithRandomPointer {
public static void main(String[] args) throws Exception {
SpecialLink link = new SpecialLink(1);
SpecialLink two = new SpecialLink(2);
SpecialLink three = new SpecialLink(3);
SpecialLink four = new SpecialLink(4);
SpecialLink five = new SpecialLink(5);
link.next = two;
two.next = three;
three.next = four;
four.next = five;
link.random = four;
two.random = five;
three.random = null;
four.random = five;
five.random=link;
SpecialLink copy = cloneSpecialLinkedList(link);
System.out.println(link);
System.out.println(copy);
}
public static SpecialLink cloneSpecialLinkedList(SpecialLink link) throws Exception{
SpecialLink temp = link;
while(temp != null){
temp.next = (SpecialLink) temp.clone();
temp = temp.next==null?temp.next:temp.next.next;
}
temp = link;
while(temp != null){
temp.next.random = temp.random!=null?temp.random.next:null;
temp = temp.next==null?temp.next:temp.next.next;
}
SpecialLink copy = link.next;
temp = link;
SpecialLink copyTemp = copy;
while(temp.next!= null && copyTemp.next != null){
temp.next = temp.next.next;
copyTemp.next = copyTemp.next.next;
temp = temp.next;
copyTemp = copyTemp.next;
}
return copy;
}
}
class SpecialLink implements Cloneable{
enum Type{
ORIGINAL,COPY
}
int val;
SpecialLink next;
SpecialLink random;
Type type;
public void setValue(int value){
this.val = value;
}
public SpecialLink addNode(int value){
return next = new SpecialLink(value);
}
public SpecialLink(int value) {
super();
this.val = value;
this.type = Type.ORIGINAL;
}
@Override
public String toString() {
SpecialLink temp = this;
StringBuilder builder = new StringBuilder();
while(temp != null){
builder.append(temp.val).append("--").append(temp.type.toString()).append("->").append(temp.random == null? null:temp.random.val).append("--").append(temp.random == null? null:temp.random.type);
builder.append(", ");
temp = temp.next;
}
return builder.toString();
}
@Override
public Object clone() throws CloneNotSupportedException {
// TODO Auto-generated method stub
SpecialLink clone = (SpecialLink) super.clone();
clone.type = Type.COPY;
return clone;
}
}
Ответ 6
Я написал код для решения @MahlerFive, который работает без отображения.
Здесь код:
private static class Node {
private String item;
private Node next;
private Node random;
}
public static Node cloneLinkedStructure(Node head) {
// make holes after each original node
for (Node p = head; p != null;) {
Node pnext = p.next;
Node hole = new Node();
hole.item = ".";
p.next = hole;
hole.next = pnext;
p = pnext;
}
Node fakeHead = new Node(); // fake new head
Node q = fakeHead;
Node p = head;
while (p != null) {
// build the new linked structure
Node oldq = q;
q = new Node();
q.item = p.item;
oldq.next = q;
q.random = p.random.next; // link to a hole
Node hole = p.next;
hole.random = q; // use link RANDOM as a backward link to new node
p = hole.next;
}
q.next = null;
Node newHead = fakeHead.next; // throw fake head
// build random links for the new linked structure
for (q = newHead; q != null; q = q.next)
q.random = q.random.random;
// delete holes to restore original linked structure
for (p = head; p != null; p = p.next)
p.next = p.next.next;
return newHead;
}
Ответ 7
1) Создайте копию node 1 и вставьте ее между node 1 и node 2 в исходном Связанном списке, создайте копию 2 и вставьте ее между 2 и 3. Продолжайте таким образом, добавьте копию N afte Nth node
2) Теперь скопируйте произвольную ссылку таким образом
original->next->arbitrary = original->arbitrary->next; /*TRAVERSE TWO NODES*/
Это работает, потому что original- > next - это не что иное, как копия оригинала, а оригинал- > произвольный- > следующий - это не что иное, как копия произвольного. 3) Теперь восстановите исходные и скопированные списки таким образом в одном цикле.
original->next = original->next->next;
copy->next = copy->next->next;
4) Убедитесь, что последний элемент original- > next равен NULL.
Сложность времени: O (n)
Вспомогательное пространство: O (1)
источник
Ответ 8
Вот реализация Java:
public static <T> RandomLinearNode<T> clone(RandomLinearNode<T> head) {
if (head == null) {
return head;
}
RandomLinearNode<T> itr = head, temp;
// insert copy nodes after each original nodes
while (itr != null) {
temp = new RandomLinearNode<T>(itr.getElement());
temp.next(itr.next());
itr.next(temp);
itr = temp.next();
}
// copy the random pointer
itr = head;
while (itr != null && itr.next() != null) {
if (itr.random() != null) {
itr.next().random(itr.random().next());
}
itr = itr.next().next();
}
// break the list into two
RandomLinearNode<T> newHead = head.next();
itr = head;
while (itr != null && itr.next() != null) {
temp = itr.next();
itr.next(temp.next());
itr = temp.next();
}
return newHead;
}
Ниже приведены модульные тесты
@Test
public void cloneLinkeListWithRandomPointerTest() {
RandomLinearNode<Integer> one = new RandomLinearNode<Integer>(1, null, null);
RandomLinearNode<Integer> two = new RandomLinearNode<Integer>(2, one, null);
RandomLinearNode<Integer> three = new RandomLinearNode<Integer>(3, two, null);
RandomLinearNode<Integer> four = new RandomLinearNode<Integer>(4, three, null);
RandomLinearNode<Integer> five = new RandomLinearNode<Integer>(5, four, four);
RandomLinearNode<Integer> six = new RandomLinearNode<Integer>(6, five, two);
RandomLinearNode<Integer> seven = new RandomLinearNode<Integer>(7, six, three);
RandomLinearNode<Integer> eight = new RandomLinearNode<Integer>(8, seven, one);
RandomLinearNode<Integer> newHead = LinkedListUtil.clone(eight);
assertThat(eight, not(sameInstance(newHead)));
assertThat(newHead.getElement(), equalTo(eight.getElement()));
assertThat(newHead.random().getElement(), equalTo(eight.random().getElement()));
assertThat(newHead.next().getElement(), equalTo(eight.next().getElement()));
assertThat(newHead.next().random().getElement(), equalTo(eight.next().random().getElement()));
assertThat(newHead.next().next().getElement(), equalTo(eight.next().next().getElement()));
assertThat(newHead.next().next().random().getElement(), equalTo(eight.next().next().random().getElement()));
assertThat(newHead.next().next().next().getElement(), equalTo(eight.next().next().next().getElement()));
assertThat(newHead.next().next().next().random().getElement(), equalTo(eight.next().next().next().random().getElement()));
}