Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

linked list

Find the middle element of a singly-linked list in a single pass

abhilash

Problem Overview

Given a singly linked list, find the middle element of the linked list in a single pass.

Example 1

  • Input: 1 -> 2 -> 3 -> 4 -> 5
  • Output: 3

Example 2

  • Input: 5 -> 9 -> 7 -> 4
  • Output: 7

Take the 2nd mid element if there are an even number of elements in the list.

Algorithm

The algorithm to use here is the two-pointer technique.

The steps of the algorithm are as follows:

  1. Initialize slow_ptr and fast_ptr to the head node.
  2. Move the slow_ptr by one node and the fast_ptr by two nodes until the fast_ptr reaches the end of the list.

Once the fast_ptr reaches the end of the list, slow_ptr will point to the middle node of the list.

  • Time Complexity: O(N)
  • Space Complexity: O(1)

Code example

public class Main{

    static class Node{
        int data;
        Node next;

        public Node(int data) {
            this.data = data;
            this.next = null;
        }
    }


    static class SinglyLinkedList{
        Node head;

        public SinglyLinkedList() {
            this.head = null;
        }

        public void addFront(int data){
            Node node = new Node(data);
            node.next = head;
            head = node;
        }

        public void printList(){
            Node temp = head;
            while(temp != null) {
                System.out.print(temp.data + " - ");
                temp = temp.next;
            }
            System.out.println("NULL");
        }

        public Node getMiddleElement(){
            if(head == null) {
                System.out.println("Empty list. Add elements to find the middle element");
                return null;
            }
            Node slowPtr = head;
            Node fastPtr = head;

            while(fastPtr != null && fastPtr.next != null){
                slowPtr = slowPtr.next;
                fastPtr = fastPtr.next.next;
            }

            return slowPtr;
        }
    }

    public static void main(String[] args) {

        SinglyLinkedList sll = new SinglyLinkedList();
        sll.addFront(5);
        sll.addFront(4);
        sll.addFront(3);
        sll.addFront(2);
        sll.addFront(1);

        sll.printList();
        System.out.println("Middle element for odd number of nodes in list is " + sll.getMiddleElement().data);

        System.out.println("----");
        sll = new SinglyLinkedList();
        sll.addFront(4);
        sll.addFront(7);
        sll.addFront(9);
        sll.addFront(5);

        sll.printList();
        System.out.println("Middle element for even number of nodes in list is " + sll.getMiddleElement().data);

    }
}

Explanation

  • Lines 3-11: Node class is defined that contains the data and the next pointer.
  • Lines 14-51: SinglyLinkedList class is defined.
  • Line 15: The head pointer is defined.
  • Lines 21-25: addFront() method is defined where we add a new node in the beginning of the list.
  • Lines 27-34: printList() method is defined where the contents of the list are printed.
  • Lines 36-50: getMiddleElement() method is defined where the algorithm defined above is implemented to find the middle element.
  • Lines 55-63: We create a linked list of odd number of nodes and find the middle element of the list.
  • Lines 65-73: We create a linked list of even number of nodes and find the middle element of the list.

RELATED TAGS

linked list
RELATED COURSES

View all Courses

Keep Exploring