Find the middle element of a singly-linked list in a single pass
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:
- Initialize
slow_ptrandfast_ptrto the head node. - Move the
slow_ptrby one node and thefast_ptrby two nodes until thefast_ptrreaches 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:
Nodeclass is defined that contains thedataand thenextpointer. - Lines 14-51:
SinglyLinkedListclass is defined. - Line 15: The
headpointer 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.