Find the Middle Element of a List

Question

Given a list of integers, find the middle element of the list.

  1. If the list is null return -1.
  2. If the list has even numbers return the lower middle, example if list has [1,2], then return 1 as the middle element.

Algorithm

  1. If list is null return -1
  2. If list has only 1 node, then return that
  3. Assign another variable to point to same node, example i
    a. Iterate the list till both next and next to next node of i is not null.
    b. While iterating, assign node to node.next and i to i.next.next.

Program

List Node

Following is the ListNode class that represent the Node in a List

package com.ekiras.ds.base;

public class ListNode {

    public int data;
    public ListNode next;

    public ListNode() {
    }

    public ListNode(int data) {
        this.data = data;
    }

    @Override
    public String toString() {
        return "ListNode{" +
                "data=" + data +
                '}';
    }
}

Main Class

package com.ekiras.ds.lists;

import com.ekiras.ds.base.ListNode;

public class MiddleElement {

    public static void main(String[] args) {
        ListNode list = new ListNode(1);
        list.next = new ListNode(2);
        list.next.next = new ListNode(3);
        list.next.next.next = new ListNode(4);
        list.next.next.next.next = new ListNode(5);
        list.next.next.next.next.next = new ListNode(6);
    }

    public static int middleElement(ListNode node) {
        if (node == null)
            return -1;

        ListNode i = node;

        while (!(i.next == null || i.next.next == null)) {
            node = node.next;
            i = i.next.next;
        }
        return node.data;
    }

}

Test Cases

package com.ekiras.ds.lists;

import com.ekiras.ds.base.ListNode;
import org.junit.Assert;
import org.junit.Test;

import static org.junit.Assert.*;

public class MiddleElementTest {

    @Test
    public void middleElement_whenNullIsPassed() {
        Assert.assertEquals(-1,MiddleElement.middleElement(null));

    }

    @Test
    public void middleElement_whenListWithOneNodeIsPassed() {
        ListNode list = new ListNode(1);
        Assert.assertEquals(1,MiddleElement.middleElement(list));

    }

    @Test
    public void middleElement_whenOddNumberOfElementsPassed() {
        ListNode list = new ListNode(1);
        list.next = new ListNode(2);
        list.next.next = new ListNode(3);
        list.next.next.next = new ListNode(4);
        list.next.next.next.next = new ListNode(5);
        assertEquals(3, MiddleElement.middleElement(list));
    }

    @Test
    public void middleElement_whenEvenNumberOfElementsPassed() {
        ListNode list = new ListNode(1);
        list.next = new ListNode(2);
        list.next.next = new ListNode(3);
        list.next.next.next = new ListNode(4);
        list.next.next.next.next = new ListNode(5);
        list.next.next.next.next = new ListNode(6);
        assertEquals(3, MiddleElement.middleElement(list));
    }
}