Effective way of finding middle element in a singly linked list

Problem

Find the middle element in a singly linked list. Obvious solution is traverse through the list once to find the length of list and then find out the middle element. This takes > O(n). Objective here is to Implement it with time complexity < O(n).

Solution

• Have 2 pointers – slow and fast. Fast point hops 2 nodes at a time but the slow one hops just one node. When the fast node reaches the end of list, the slow node points the middle node.
• Time complexity – O(n/2).
• Java based implementation with unit tests given below.

package com.computepatterns.problemsolving.linkedlist;

/**
 * Finding middle element in singly linked list with effective time complexity.
 * Time complexity - O(n/2)
 */
public class FindingMiddleElementLinkedList {
    /**
     * Represents nodes in the linked list.
     */
    public static class Node{
        private int value;
        private Node next;

        public Node(int value) {
            this.value = value;
        }

        public int getValue() {
            return value;
        }

        Node getNext() {
            return next;
        }


        public void setNext(Node next) {
            this.next = next;
        }
    }

    private Node start;

    public void setStart(Node start) {
        this.start = start;
    }

    /**
     * Print the content of list.
     */
    public void printList(){
        Node currentNode = start;
        StringBuilder toPrint = new StringBuilder();
        while(null != currentNode){
            toPrint.append(currentNode.getValue() + ",");
            currentNode = currentNode.next;
        }

        System.out.println(toPrint);
    }

    public Node findMiddleNode(){
        /* Initialize slow and faster pointers. Fast pointer jumps 2 nodes in single loop */
        // Note - Idea is when the fast pointer reaches the end, the slow pointer should show the middle one.
        Node slowPtr = start;
        Node fastPtr = start;

        /* Loop through the list and and increment pointers. */
        while(true){
            // Jumps 2 nodes in a single iteration.
            if(null != fastPtr.getNext()) {
                fastPtr = fastPtr.getNext().getNext();
            }else{
                // Case - Odd length list exist condition.
                break;
            }

            // Case - Even length list exit condition.
            if(null == fastPtr){
                break;
            }

            // Standard increment.
            slowPtr = slowPtr.getNext();
        }

        return slowPtr;
    }
}

package com.computepatterns.problemsolving.linkedlist;

import org.junit.After;
import org.junit.Before;
import org.junit.Test;
import static org.junit.Assert.*;

/**
 * Test finding middle element in singly linked list with odd and even length list
 */
public class FindingMiddleElementLinkedListTest {

    @Test
    public void testFindMiddleNode_odd_listlength_case() throws Exception {
        FindingMiddleElementLinkedList linkedList = new FindingMiddleElementLinkedList();

        FindingMiddleElementLinkedList.Node node1 = new FindingMiddleElementLinkedList.Node(1);
        FindingMiddleElementLinkedList.Node node2 = new FindingMiddleElementLinkedList.Node(2);
        FindingMiddleElementLinkedList.Node node3 = new FindingMiddleElementLinkedList.Node(3);
        FindingMiddleElementLinkedList.Node node4 = new FindingMiddleElementLinkedList.Node(4);
        FindingMiddleElementLinkedList.Node node5 = new FindingMiddleElementLinkedList.Node(5);
        FindingMiddleElementLinkedList.Node node6 = new FindingMiddleElementLinkedList.Node(6);
        FindingMiddleElementLinkedList.Node node7 = new FindingMiddleElementLinkedList.Node(7);

        node1.setNext(node2);
        node2.setNext(node3);
        node3.setNext(node4);
        node4.setNext(node5);
        node5.setNext(node6);
        node6.setNext(node7);

        linkedList.setStart(node1);

        // Find middle element.
        FindingMiddleElementLinkedList.Node middleNode = linkedList.findMiddleNode();
        assertEquals(4, middleNode.getValue());
    }

    @Test
    public void testFindMiddleNode_even_listlength_case() throws Exception {
        FindingMiddleElementLinkedList linkedList = new FindingMiddleElementLinkedList();

        FindingMiddleElementLinkedList.Node node1 = new FindingMiddleElementLinkedList.Node(1);
        FindingMiddleElementLinkedList.Node node2 = new FindingMiddleElementLinkedList.Node(2);
        FindingMiddleElementLinkedList.Node node3 = new FindingMiddleElementLinkedList.Node(3);
        FindingMiddleElementLinkedList.Node node4 = new FindingMiddleElementLinkedList.Node(4);
        FindingMiddleElementLinkedList.Node node5 = new FindingMiddleElementLinkedList.Node(5);
        FindingMiddleElementLinkedList.Node node6 = new FindingMiddleElementLinkedList.Node(6);
        FindingMiddleElementLinkedList.Node node7 = new FindingMiddleElementLinkedList.Node(7);
        FindingMiddleElementLinkedList.Node node8 = new FindingMiddleElementLinkedList.Node(8);
        FindingMiddleElementLinkedList.Node node9 = new FindingMiddleElementLinkedList.Node(9);
        FindingMiddleElementLinkedList.Node node10 = new FindingMiddleElementLinkedList.Node(10);

        node1.setNext(node2);
        node2.setNext(node3);
        node3.setNext(node4);
        node4.setNext(node5);
        node5.setNext(node6);
        node6.setNext(node7);
        node7.setNext(node8);
        node8.setNext(node9);
        node9.setNext(node10);

        linkedList.setStart(node1);

        // Find middle element.
        FindingMiddleElementLinkedList.Node middleNode = linkedList.findMiddleNode();
        assertEquals(5, middleNode.getValue());

    }
}

Link to source code

 Reference

• http://www.geeksforgeeks.org/write-a-c-function-to-print-the-middle-of-the-linked-list/