найти средний элемент связанного списка

[rzen]

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

а как бы вы такую задачу решили практически?

да, чуть не забыл, язык жаба.

[valchkou]

а как бы вы такую задачу решили практически?
да, чуть не забыл, язык жаба.

если я правильно понял задачу то можно так

Code: Select all

	
     List<String> list = new LinkedList();
     list.add("firs");
     list.add("middle");
     list.add("last");
	
     // поиск среднего элемента	
     int idx = list.size()/2;
     String s = list.get(idx);
     System.out.println(s); -> middle

[Flash-04]

давайте вначале определим что есть "средний элемент" для списка из чётного кол-ва элементов? ну например список из двух элементов

[fruit6]

один цикл.
хранить ссылку на элемент списка и менять ее на element.nextElement() на каждый четный проход в цикле.
начальное значение ссылки - первый элемент списка.

[rzen]

да, это был первый же предложенный вариант на что интервьющица сообщила что у связанного списка нет метода size() не знаю было ли это её заблуждение или дополнительная вводная на засыпку но такое решение небыло принято

[fruit6]

а как бы вы такую задачу решили практически?
да, чуть не забыл, язык жаба.

если я правильно понял задачу то можно так

Code: Select all

	
     List<String> list = new LinkedList();
     list.add("firs");
     list.add("middle");
     list.add("last");
	
     // поиск среднего элемента	
     int idx = list.size()/2;
     String s = list.get(idx);
     System.out.println(s); -> middle

подразумевается что get() & size() недоступны. только ссылка на первый элемент.

[rzen]

один цикл.
хранить ссылку на элемент списка и менять ее на element.nextElement() на каждый четный проход в цикле.
начальное значение ссылки - первый элемент списка.

не вижу как можно обойти полный проход по всем элементам полтора раза.

[avitya]

В первом посте написан квадратичный алгоритм (цикл в цикле), в то время, как от вас требуется иметь два итератора, один двигать на два элемента, другой на один. Так как это связанный список, то у него метода get(idх) нету. Кроме того, большинство реализаций для связанного списка оптимизируют функцию splice(), в результате которой size() становится линейным (есть и обратные, где size() O(1), а splice() линейная).
Итого, итератор посещает, как правильно заметили, 1.5N элементов, что все ещё О(Н)...

[valchkou]

да, это был первый же предложенный вариант на что интервьющица сообщила что у связанного списка нет метода size() не знаю было ли это её заблуждение или дополнительная вводная на засыпку но такое решение небыло принято

Если она имела ввиду, что "a давайте предположим, что нет метода size()",
тогда сразу встает вопрос, а может это и не жава вовсе, может я вам тогда по русски напишу
- беру значит список, отмеряю на глаз половину и уякс топором

[rzen]

мне интересно не окажется ли в практическом смысле проще сконвертировать список в коллекцию и уже искать серединный элемент в ней? на конвертацию потратится один проход, соберутся ссылки, будут потери на пере-аллокацию памяти для коллекции в процессе наполнения, потеря памяти на ссылки на объекты и собссно всё, какие ещё потери?

[fruit6]

Code: Select all

public class LinkedListNode {
	
	private LinkedListNode nextElement;
	private int id; // for demo purpose
	
	public LinkedListNode(LinkedListNode next, int id) {
		this.nextElement = next;
		this.id = id;
	}
	
	public LinkedListNode nextElement() {
		return nextElement;
	}
	
	public static void main(String[] args) {
		LinkedListNode node7 = new LinkedListNode(null, 7);
		LinkedListNode node6 = new LinkedListNode(node7, 6);
		LinkedListNode node5 = new LinkedListNode(node6, 5);
		LinkedListNode node4 = new LinkedListNode(node5, 4);
		LinkedListNode node3 = new LinkedListNode(node4, 3);
		LinkedListNode node2 = new LinkedListNode(node3, 2);
		LinkedListNode node1 = new LinkedListNode(node2, 1);
		
		// List: node1 -> node2 -> node3 -> node4 -> node5 
		LinkedListNode middle = findMiddleElement(node1);
		System.out.println("middle element id: " + middle.id);
	}
	
	/**
	 * 
	 * @param firstElement not null ref to first node.
	 * @return
	 */
	public static LinkedListNode findMiddleElement(LinkedListNode firstElement) {
		LinkedListNode middle = firstElement;
		LinkedListNode currentNode = firstElement;
		boolean even = true;
		while (currentNode.nextElement() != null) {
			currentNode = currentNode.nextElement();
			if (even)
				even = false;
			else {
				even = true;
				middle = middle.nextElement();
			}
		}
		
		return middle;
	}
}

[avitya]

С этим решением несколько проблем.
1. Это потеря памяти
2. Чтоб скопировать список, уже Н операций надо сделать
3. Новую коллекцию надо удалить
4. Нужно изворачиваться, скажем новая коллекция должна быть скорее всего коллекцией итераторов (то есть собрать придется Н+1 объект как минимум).
В реальности, конечно, если такое надо делать, то не нужно список использовать, но задача на то и задача

[valchkou]

Так как это связанный список, то у него метода get(idх) нету.

А на яве есть, хотя он и линейный но есть, зачем велосипед придумывать ? это ж ява

[avitya]

вы упускаете смысл слова задача

[rzen]

С этим решением несколько проблем.
1. Это потеря памяти
2. Чтоб скопировать список, уже Н операций надо сделать
3. Новую коллекцию надо удалить
4. Нужно изворачиваться, скажем новая коллекция должна быть скорее всего коллекцией итераторов (то есть собрать придется Н+1 объект как минимум).
В реальности, конечно, если такое надо делать, то не нужно список использовать, но задача на то и задача

потеря памяти да, но и не придется полтора раза проходить все элементы списка.

про изворачивание не понял, а удаление коллекции не вижу проблематичности.

что касается того что не надо использовать список это факт, но да, на то она и задача

[SVK]

потеря памяти да, но и не придется полтора раза проходить все элементы списка.

Если список обозримого размера, то полтора прохода по нему - это ерунда, о которой не стоит переживать.
А вот если список действительно гигантский, то скорее уж его промежуточная конвертация во что угодно выльется в катастрофу от потери памяти. И я сильно сомневаюсь, что конвертация N элементов списка пройдет быстрее, чем 1.5*N простых прохода по next()

[АццкоМото]

Да просто же. Точно также, как ищутся петли в связанном списке: начинается траверсал с начала двумя указателями, один передвигается на один элемент вперед, второй - на два. как второй уперся в конец, первый - в середине

[rzen]

потеря памяти да, но и не придется полтора раза проходить все элементы списка.

Если список обозримого размера, то полтора прохода по нему - это ерунда, о которой не стоит переживать.
А вот если список действительно гигантский, то скорее уж его промежуточная конвертация во что угодно выльется в катастрофу от потери памяти. И я сильно сомневаюсь, что конвертация N элементов списка пройдет быстрее, чем 1.5*N простых прохода по next()

"конвертация" это тривиальная манипуляция ссылками, с чего бы ей стать катастрофой?

[avitya]

В основном, что надо выделить массив размера Н * размер элемента. Если у вас миллиард элементов....

[АццкоМото]

Короче...

Code: Select all

struct node* findMiddle(struct node* head)
{
  struct node *slow_ptr = head;
  struct node *fast_ptr = head;
 
  if(head!=NULL) {
       while((fast_ptr->next)!=NULL &&
               (fast_ptr->next->next)!=NULL) {
          fast_ptr = fast_ptr->next->next;
          slow_ptr = slow_ptr->next;
       }
       return slow_ptr;
  } else {
    return NULL;
  }
}

[rzen]

В основном, что надо выделить массив размера Н * размер элемента. Если у вас миллиард элементов....

В коллекции хранятся ссылки на элементы, не сами элементы.

[Reds]

Java:

Code: Select all

public class FindMiddleElementOfLinkedList {

	public Node<Integer> findMiddleElementOfLinkedList(Node<Integer> head) {
		if (head == null) {
			throw new IllegalArgumentException("head is null");
		}

		Node<Integer> result = head;
		Node<Integer> doubleJumpNode = head;
		while (doubleJumpNode.next != null && doubleJumpNode.next.next != null) {
			doubleJumpNode = doubleJumpNode.next.next;
			result = result.next;
		}

		return result;

	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Node<Integer> head = new Node<Integer>(1);

		Node<Integer> node2 = new Node<Integer>(2);
		head.next = node2;

		Node<Integer> node3 = new Node<Integer>(3);
		node2.next = node3;

		Node<Integer> node4 = new Node<Integer>(4);
		node3.next = node4;

		Node<Integer> node5 = new Node<Integer>(5);
		node4.next = node5;

		Node<Integer> node6 = new Node<Integer>(6);
		node5.next = node6;

		Node<Integer> node7 = new Node<Integer>(7);
		node6.next = node7;

		Node<Integer> node8 = new Node<Integer>(8);
		node7.next = node8;

		Node<Integer> node9 = new Node<Integer>(9);
		node8.next = node9;

		FindMiddleElementOfLinkedList service = new FindMiddleElementOfLinkedList();
		Node<Integer> middleOne = service.findMiddleElementOfLinkedList(head);
		
	    System.out.println(middleOne.value);
		

	}

	private static class Node<T> {
		public T value;
		public Node<T> next;

		public Node(T value) {
			super();
			this.value = value;
		}

	}

}

[avitya]

В основном, что надо выделить массив размера Н * размер элемента. Если у вас миллиард элементов....

В коллекции хранятся ссылки на элементы, не сами элементы.

Я понимаю, но ссылка это тоже память. В простейшем случае указатель -- 4 байта (в 32битнойсистеме). И вот вы затребовали 4 гигабайта последовательной памяти

[rzen]

В основном, что надо выделить массив размера Н * размер элемента. Если у вас миллиард элементов....

В коллекции хранятся ссылки на элементы, не сами элементы.

Я понимаю, но ссылка это тоже память. В простейшем случае указатель -- 4 байта (в 32битнойсистеме). И вот вы затребовали 4 гигабайта последовательной памяти

как минимум такое количество памяти (and then some) уже размещено на список. времена последовательного доступа (и сортировки на магнитной ленте) давно прошли, слава всевышнему.

[avitya]

Ну разница в том, что для списка не нужна последовательная память (одно из редких преимуществ списка). Во вторых, если у вас всего 4 (32 битная система), то как бы всё... Если со всякими ПАЕ и т.д. -- то всё равно 4г выделить последовательно это время и т.д. Выделите на своей машине массив из милларда элементов.