вопрос интервью со связанным списком

Question

Этот вопрос был задан в интервью. Кто-нибудь может мне помочь в реализации в Java? Учитывая 2 связанных списка (которые не должны иметь уникальных элементов) найти точку пересечения в форме Y (это может быть где угодно - середина или хвост)

Answer 1

Если длина списков равна O(N), это решение равно O(N) с O(1) пробелом.

FUNCTION length(LIST list) : INT
// returns number of nodes until the end of the list

FUNCTION skip(LIST list, INT k) : LIST
// return the sublist of list, skipping k nodes

FUNCTION intersection(LIST list1, list2) : LIST
// returns the sublist where the two lists intersects
  INT n1 = length(list1);
  INT n2 = length(list2);

  IF (n1 > n2) THEN
     list1 = skip(list1, n1-n2)
  ELSE
     list2 = skip(list2, n2-n1)

  WHILE (list1 != list2)
    list1 = skip(list1, 1)
    list2 = skip(list2, 1)

  RETURN list1

По сути, пройдитесь по каждому списку, чтобы найти количество узлов. Затем пропустите достаточно элементов из более длинного списка, чтобы теперь у вас были списки одинаковой длины. Затем, синхронно, двигайтесь вперед шаг за шагом, пока не встретятся два списка.

Answer 2

http://java.sun.com/docs/books/tutorial/collections/interfaces/set.html

У меня нет хорошего примера в данный момент, но я думаю, что он ссылается на это:

«Пересечение двух наборов - это набор, содержащий только элементы, общие для обоих наборов».

Где «наборы» также могут быть списками и т. Д.

Java имеет встроенные методы для этого.

Скажем, у вас есть список List, вы бы сделали что-то вроде этого:

list.removeAll (песни2); * +1014 *

или

list.retainAll (песни2);

retainAll, вы дадите вам «пересечение», removeAll даст вам разницу между двумя списками.

Answer 3

Согласно вопросу @Lord Torgamus, вот предложенный алгоритм java .

Предположим, у вас есть два объекта java Collection (и LinkedList , как разработчик List , также является разработчиком Collection).Чтобы найти их пересечение, вам нужно всего лишь вызвать Collection # retainAll метод для первого объекта, предоставив второй в качестве аргумента.