Намерете средния елемент на свързан списък в Java

1. Общ преглед

В този урок ще обясним как да намерим средния елемент на свързан списък в Java.

Ще представим основните проблеми в следващите раздели и ще покажем различни подходи за решаването им.

2. Следене на размера

Този проблем може лесно да бъде решен само чрез проследяване на размера, когато добавяме нови елементи към списъка . Ако знаем размера, знаем и къде е средният елемент, така че решението е тривиално.

Нека да видим пример, използващ изпълнението на Java на LinkedList :

public static Optional findMiddleElementLinkedList( LinkedList linkedList) { if (linkedList == null || linkedList.isEmpty()) { return Optional.empty(); } return Optional.of(linkedList.get( (linkedList.size() - 1) / 2)); }

Ако проверим вътрешния код на класа LinkedList , можем да видим, че в този пример просто обхождаме списъка, докато стигнем до средния елемент:

Node node(int index) { if (index > 1)) { Node x = first; for (int i = 0; i < index; i++) { x = x.next; } return x; } else { Node x = last; for (int i = size - 1; i > index; i--) { x = x.prev; } return x; } }

3. Намиране на средата, без да се знае размерът

Много често се срещаме с проблеми, при които имаме само главен възел на свързан списък и трябва да намерим средния елемент. В този случай не знаем размера на списъка, което прави този проблем по-труден за решаване.

Ще покажем в следващите раздели няколко подхода за решаване на този проблем, но първо трябва да създадем клас, който да представлява възел от списъка.

Нека създадем клас Node , който съхранява String стойности:

public static class Node { private Node next; private String data; // constructors/getters/setters public boolean hasNext() { return next != null; } public void setNext(Node next) { this.next = next; } public String toString() { return this.data; } }

Също така, ние ще използваме този помощен метод в нашите тестови случаи, за да създадем единично свързан списък, използвайки само нашите възли:

private static Node createNodesList(int n) { Node head = new Node("1"); Node current = head; for (int i = 2; i <= n; i++) { Node newNode = new Node(String.valueOf(i)); current.setNext(newNode); current = newNode; } return head; }

3.1. Първо намиране на размера

Най-простият подход за справяне с този проблем е първо да се намери размерът на списъка, а след това да се следва същия подход, който използвахме преди - да се итерира до средния елемент.

Нека да видим това решение в действие:

public static Optional findMiddleElementFromHead(Node head) { if (head == null) { return Optional.empty(); } // calculate the size of the list Node current = head; int size = 1; while (current.hasNext()) { current = current.next(); size++; } // iterate till the middle element current = head; for (int i = 0; i < (size - 1) / 2; i++) { current = current.next(); } return Optional.of(current.data()); }

Както виждаме, този код се повтаря два пъти в списъка. Следователно това решение има лоша производителност и не се препоръчва .

3.2. Намиране на средния елемент в едно преминаване итеративно

Сега ще подобрим предишното решение, като намерим средния елемент само с една итерация върху списъка.

За да го направим итеративно, имаме нужда от два указателя, които да прелистват списъка едновременно. Единият указател ще напредва по 2 възела във всяка итерация, а другият указател ще пренася само по един възел на итерация .

Когато по-бързият указател достигне края на списъка, по-бавният указател ще бъде в средата:

public static Optional findMiddleElementFromHead1PassIteratively(Node head) { if (head == null) { return Optional.empty(); } Node slowPointer = head; Node fastPointer = head; while (fastPointer.hasNext() && fastPointer.next().hasNext()) { fastPointer = fastPointer.next().next(); slowPointer = slowPointer.next(); } return Optional.ofNullable(slowPointer.data()); }

Можем да тестваме това решение с обикновен единичен тест, като използваме списъци с нечетен и четен брой елементи:

@Test public void whenFindingMiddleFromHead1PassIteratively_thenMiddleFound() { assertEquals("3", MiddleElementLookup .findMiddleElementFromHead1PassIteratively( createNodesList(5)).get()); assertEquals("2", MiddleElementLookup .findMiddleElementFromHead1PassIteratively( reateNodesList(4)).get()); }

3.3. Намирането на средния елемент в едно преминаване рекурсивно

Друг начин за решаване на този проблем за един проход е използването на рекурсия. Можем да повторим до края на списъка, за да знаем размера, а при обратно извикване просто броим до половината от размера.

За да направим това в Java, ще създадем спомагателен клас, за да запазим препратките към размера на списъка и средния елемент по време на изпълнението на всички рекурсивни повиквания:

private static class MiddleAuxRecursion { Node middle; int length = 0; }

Сега, нека приложим рекурсивния метод:

private static void findMiddleRecursively( Node node, MiddleAuxRecursion middleAux) { if (node == null) { // reached the end middleAux.length = middleAux.length / 2; return; } middleAux.length++; findMiddleRecursively(node.next(), middleAux); if (middleAux.length == 0) { // found the middle middleAux.middle = node; } middleAux.length--; }

И накрая, нека създадем метод, който извиква рекурсивния:

public static Optional findMiddleElementFromHead1PassRecursively(Node head) { if (head == null) { return Optional.empty(); } MiddleAuxRecursion middleAux = new MiddleAuxRecursion(); findMiddleRecursively(head, middleAux); return Optional.of(middleAux.middle.data()); }

Отново можем да го тестваме по същия начин, както преди:

@Test public void whenFindingMiddleFromHead1PassRecursively_thenMiddleFound() { assertEquals("3", MiddleElementLookup .findMiddleElementFromHead1PassRecursively( createNodesList(5)).get()); assertEquals("2", MiddleElementLookup .findMiddleElementFromHead1PassRecursively( createNodesList(4)).get()); }

4. Заключение

В тази статия представихме проблема с намирането на средния елемент на свързан списък в Java и показахме различни начини за решаването му.

Започнахме от най-простия подход, където проследихме размера и след това продължихме с решенията за намиране на средния елемент от главния възел на списъка.

Както винаги, пълният изходен код на примерите е достъпен в GitHub.