BAEL-1773 Find the middle element of a Linked List. (eugenp#4425)

marcos-lg · pedja4 · commit 0a3d212a2a32 · 2018-06-08T07:35:46.000+02:00
* BAEL-1773 - find middle element of linked list

* changes from review

* changes from review

* find middle element in linked list

* typo
diff --git a/core-java/src/main/java/com/baeldung/linkedlist/MiddleElementLookup.java b/core-java/src/main/java/com/baeldung/linkedlist/MiddleElementLookup.java
@@ -1,10 +1,20 @@
 package com.baeldung.linkedlist;
 
-import com.baeldung.linkedlist.LinkedList.Node;
+import java.util.LinkedList;
+
+import com.baeldung.linkedlist.Node;
 
 public class MiddleElementLookup {
 
-    public static String findMiddleElement(Node head) {
+    public static String findMiddleElementLinkedList(LinkedList<String> linkedList) {
+        if (linkedList == null || linkedList.isEmpty()) {
+            return null;
+        }
+
+        return linkedList.get((linkedList.size() - 1) / 2);
+    }
+
+    public static String findMiddleElementFromHead(Node head) {
         if (head == null) {
             return null;
         }
@@ -26,7 +36,7 @@ public static String findMiddleElement(Node head) {
         return current.data();
     }
 
-    public static String findMiddleElement1PassRecursively(Node head) {
+    public static String findMiddleElementFromHead1PassRecursively(Node head) {
         if (head == null) {
             return null;
         }
@@ -53,7 +63,7 @@ private static void findMiddleRecursively(Node node, MiddleAuxRecursion middleAu
         middleAux.length--;
     }
 
-    public static String findMiddleElement1PassIteratively(Node head) {
+    public static String findMiddleElementFromHead1PassIteratively(Node head) {
         if (head == null) {
             return null;
         }
diff --git a/core-java/src/main/java/com/baeldung/linkedlist/Node.java b/core-java/src/main/java/com/baeldung/linkedlist/Node.java
@@ -0,0 +1,34 @@
+package com.baeldung.linkedlist;
+
+public class Node {
+    private Node next;
+    private String data;
+
+    public Node(String data) {
+        this.data = data;
+    }
+
+    public String data() {
+        return data;
+    }
+
+    public void setData(String data) {
+        this.data = data;
+    }
+
+    public boolean hasNext() {
+        return next != null;
+    }
+
+    public Node next() {
+        return next;
+    }
+
+    public void setNext(Node next) {
+        this.next = next;
+    }
+
+    public String toString() {
+        return this.data;
+    }
+}
diff --git a/core-java/src/test/java/com/baeldung/linkedlist/MiddleElementLookupUnitTest.java b/core-java/src/test/java/com/baeldung/linkedlist/MiddleElementLookupUnitTest.java
@@ -2,51 +2,46 @@
 
 import static org.junit.Assert.assertEquals;
 
+import java.util.LinkedList;
+
 import org.junit.Test;
 
 public class MiddleElementLookupUnitTest {
 
     @Test
-    public void whenFindingMiddle_thenMiddleFound() {
-        String middle = MiddleElementLookup.findMiddleElement(createList(5).head());
-        assertEquals("3", middle);
-
-        middle = MiddleElementLookup.findMiddleElement(createList(4).head());
-        assertEquals("2", middle);
+    public void whenFindingMiddleLinkedList_thenMiddleFound() {
+        assertEquals("3", MiddleElementLookup.findMiddleElementLinkedList(createLinkedList(5)));
+        assertEquals("2", MiddleElementLookup.findMiddleElementLinkedList(createLinkedList(4)));
     }
 
     @Test
-    public void whenFindingMiddle1PassRecursively_thenMiddleFound() {
-        String middle = MiddleElementLookup.findMiddleElement1PassRecursively(createList(5).head());
-        assertEquals("3", middle);
-
-        middle = MiddleElementLookup.findMiddleElement1PassRecursively(createList(4).head());
-        assertEquals("2", middle);
+    public void whenFindingMiddleFromHead_thenMiddleFound() {
+        assertEquals("3", MiddleElementLookup.findMiddleElementFromHead(createNodesList(5)));
+        assertEquals("2", MiddleElementLookup.findMiddleElementFromHead(createNodesList(4)));
     }
 
     @Test
-    public void whenFindingMiddle1PassIteratively_thenMiddleFound() {
-        String middle = MiddleElementLookup.findMiddleElement1PassIteratively(createList(5).head());
-        assertEquals("3", middle);
+    public void whenFindingMiddleFromHead1PassRecursively_thenMiddleFound() {
+        assertEquals("3", MiddleElementLookup.findMiddleElementFromHead1PassRecursively(createNodesList(5)));
+        assertEquals("2", MiddleElementLookup.findMiddleElementFromHead1PassRecursively(createNodesList(4)));
+    }
 
-        middle = MiddleElementLookup.findMiddleElement1PassIteratively(createList(4).head());
-        assertEquals("2", middle);
+    @Test
+    public void whenFindingMiddleFromHead1PassIteratively_thenMiddleFound() {
+        assertEquals("3", MiddleElementLookup.findMiddleElementFromHead1PassIteratively(createNodesList(5)));
+        assertEquals("2", MiddleElementLookup.findMiddleElementFromHead1PassIteratively(createNodesList(4)));
     }
 
     @Test
     public void whenListEmptyOrNull_thenMiddleNull() {
-        String middle = MiddleElementLookup.findMiddleElement(null);
-        assertEquals(null, middle);
-
-        middle = MiddleElementLookup.findMiddleElement1PassIteratively(null);
-        assertEquals(null, middle);
-
-        middle = MiddleElementLookup.findMiddleElement1PassRecursively(null);
-        assertEquals(null, middle);
+        assertEquals(null, MiddleElementLookup.findMiddleElementLinkedList(null));
+        assertEquals(null, MiddleElementLookup.findMiddleElementFromHead(null));
+        assertEquals(null, MiddleElementLookup.findMiddleElementFromHead1PassIteratively(null));
+        assertEquals(null, MiddleElementLookup.findMiddleElementFromHead1PassRecursively(null));
     }
 
-    private static LinkedList createList(int n) {
-        LinkedList list = new LinkedList();
+    private static LinkedList<String> createLinkedList(int n) {
+        LinkedList<String> list = new LinkedList<>();
 
         for (int i = 1; i <= n; i++) {
             list.add(String.valueOf(i));
@@ -55,4 +50,17 @@ private static LinkedList createList(int n) {
         return list;
     }
 
+    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;
+    }
+
 }
