How to Find Middle Element of LinkedList in One Pass
Here is a complete Java program to find the middle node of Linked List in Java. Remember LinkedList class here is our custom class and don’t confuse this class with java.util.LinkedList is a popular Collection class in Java.
In this Java program, our class LinkedList represents a linked list data structure that contains a collection of the node and has a head and tail.
Each node contains data and addresses part. The main method of LinkedListTest class is used to simulate the problem, where we created Linked List and added few elements on it and then iterate over them to find the middle element of linked list in one pass in Java.
If you want to learn more about linked list data structure and different types of linked lists like a singly linked list, doubly linked list, circularly linked list et all then you can also check theAlgorithms and Data Structures - Part 1 and 2courses on Pluralsight. One of the better course to learn data structure and algorithms.
Btw, you would need a Pluralsight membership to access this course. If you are not a member, you can still access this course by using the 10-day free pass provided by Pluralsight to explorer its portal and online courses.
In this Java program, our class LinkedList represents a linked list data structure that contains a collection of the node and has a head and tail.
Each node contains data and addresses part. The main method of LinkedListTest class is used to simulate the problem, where we created Linked List and added few elements on it and then iterate over them to find the middle element of linked list in one pass in Java.
If you want to learn more about linked list data structure and different types of linked lists like a singly linked list, doubly linked list, circularly linked list et all then you can also check theAlgorithms and Data Structures - Part 1 and 2courses on Pluralsight. One of the better course to learn data structure and algorithms.
Btw, you would need a Pluralsight membership to access this course. If you are not a member, you can still access this course by using the 10-day free pass provided by Pluralsight to explorer its portal and online courses.
Java Program to Find the Middle Node of a Linked list in a Single-pass
import test.LinkedList.Node;
/**
* Java program to find middle element of linked list in one pass.
* In order to find middle element of a linked list
* we need to find the length first but since we can only
* traverse linked list one time, we will have to use two pointers
* one which we will increment on each iteration while
* other which will be incremented every second iteration.
* So when the first pointer will point to the end of a
* linked list, second will be pointing to the middle
* element of a linked list
*
* @author Javin Paul
*/
public class LinkedListTest {
public static void main[String args[]] {
//creating LinkedList with 5 elements including head
LinkedList linkedList = new LinkedList[];
LinkedList.Node head = linkedList.head[];
linkedList.add[ new LinkedList.Node["1"]];
linkedList.add[ new LinkedList.Node["2"]];
linkedList.add[ new LinkedList.Node["3"]];
linkedList.add[ new LinkedList.Node["4"]];
//finding middle element of LinkedList in single pass
LinkedList.Node current = head;
int length = 0;
LinkedList.Node middle = head;
while[current.next[] != null]{
length++;
if[length%2 ==0]{
middle = middle.next[];
}
current = current.next[];
}
if[length%2 == 1]{
middle = middle.next[];
}
System.out.println["length of LinkedList: " + length];
System.out.println["middle element of LinkedList : " + middle];
}
}
class LinkedList{
private Node head;
private Node tail;
public LinkedList[]{
this.head = new Node["head"];
tail = head;
}
public Node head[]{
return head;
}
public void add[Node node]{
tail.next = node;
tail = node;
}
public static 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 Node next[] {
return next;
}
public void setNext[Node next] {
this.next = next;
}
public String toString[]{
return this.data;
}
}
}
Output:
length of LinkedList: 4
the middle element of LinkedList: 2
/**
* Java program to find middle element of linked list in one pass.
* In order to find middle element of a linked list
* we need to find the length first but since we can only
* traverse linked list one time, we will have to use two pointers
* one which we will increment on each iteration while
* other which will be incremented every second iteration.
* So when the first pointer will point to the end of a
* linked list, second will be pointing to the middle
* element of a linked list
*
* @author Javin Paul
*/
public class LinkedListTest {
public static void main[String args[]] {
//creating LinkedList with 5 elements including head
LinkedList linkedList = new LinkedList[];
LinkedList.Node head = linkedList.head[];
linkedList.add[ new LinkedList.Node["1"]];
linkedList.add[ new LinkedList.Node["2"]];
linkedList.add[ new LinkedList.Node["3"]];
linkedList.add[ new LinkedList.Node["4"]];
//finding middle element of LinkedList in single pass
LinkedList.Node current = head;
int length = 0;
LinkedList.Node middle = head;
while[current.next[] != null]{
length++;
if[length%2 ==0]{
middle = middle.next[];
}
current = current.next[];
}
if[length%2 == 1]{
middle = middle.next[];
}
System.out.println["length of LinkedList: " + length];
System.out.println["middle element of LinkedList : " + middle];
}
}
class LinkedList{
private Node head;
private Node tail;
public LinkedList[]{
this.head = new Node["head"];
tail = head;
}
public Node head[]{
return head;
}
public void add[Node node]{
tail.next = node;
tail = node;
}
public static 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 Node next[] {
return next;
}
public void setNext[Node next] {
this.next = next;
}
public String toString[]{
return this.data;
}
}
}
Output:
length of LinkedList: 4
the middle element of LinkedList: 2
That’s all on How to find the middle element of LinkedList in one pass. As I said this is a good interview question to separate programmers from non-programmers. Also, the technique mentioned here to find the middle node of LinkedList can be used to find the 3rd element from Last or nth element from last in a LinkedList as well.
Further Learning
Data Structures and Algorithms: Deep Dive Using Java
Algorithms and Data Structures - Part 1 and 2
Introduction to Algorithms by Thomas H. Corman
Grokking the Coding Interview: Patterns for Coding Questions
If you like this article and would like to try out a couple of more challenging programming exercise, then take a look at following programming questions from various Interviews :
Thanks for reading this coding interview question so far. If you like this String interview question then please share it with your friends and colleagues. If you have any questions or feedback then please drop a comment.
P. S. - If you are looking for some Free Algorithms courses to improve your understanding of Data Structure and Algorithms, then you should also check this list of Free Data Structure and Algorithms Courses for Programmers.
Further Learning
Data Structures and Algorithms: Deep Dive Using Java
Algorithms and Data Structures - Part 1 and 2
Introduction to Algorithms by Thomas H. Corman
Grokking the Coding Interview: Patterns for Coding Questions
If you like this article and would like to try out a couple of more challenging programming exercise, then take a look at following programming questions from various Interviews :
- How to check if LinkedList contains any cycle in Java? [solution]
- How to search an element in an array in Java? [solution]
- How to sort an array using bubble sort algorithm? [algorithm]
- How to calculate Sum of Digits of a number in Java? [Solution]
- Write a program to find first non repeated characters from String in Java? [program]
- How to check if a number is binary in Java? [answer]
- Write a program to check if a number is Prime or not? [solution]
- How to prevent Deadlock in Java? [solution]
- How to find the largest prime factor of a number in Java? [solution]
- How to calculate a factorial using recursion in Java? [algorithm]
- How to declare and initialize a two-dimensional array in Java? [solution]
- Write a method to count occurrences of a character in String? [Solution]
- How to check if a number is Armstrong number or not? [solution]
- Write a Program remove duplicates from an array without using Collection API? [program]
- How to reverse String in Java without using API methods? [Solution]
- Write a method to remove duplicates from ArrayList in Java? [Solution]
- Write a program to check if a number isa Palindromeor not? [program]
- Write a program to check if the Array contains a duplicate number or not? [Solution]
- How to find the Fibonacci sequence up to a given number? [solution]
- Write a program to find a missing number in a sorted array? [algorithm]
- 10 Points about Array in Java? [must-know facts]
- How to find the top two maximum on integer array in Java? [solution]
- Write a method to check if two String are Anagram of each other? [method]
- How to find the largest and smallest number in an array? [solution]
- Write a function to find the middle element of the linked list in one pass? [solution]
- How to solve the Producer-Consumer Problem in Java. [solution]
- Write a Program to Check if a number is Power of Two or not? [program]
Thanks for reading this coding interview question so far. If you like this String interview question then please share it with your friends and colleagues. If you have any questions or feedback then please drop a comment.
P. S. - If you are looking for some Free Algorithms courses to improve your understanding of Data Structure and Algorithms, then you should also check this list of Free Data Structure and Algorithms Courses for Programmers.