Howdo you find the middle element of LinkedList in one pass is a programming question often asked Java and non-Java programmers in telephonic Interview. This question is similar to checking palindrome or
calculating the factorial, where Interviewer sometimes also ask to write code. In order to answer this question candidate must be familiar with LinkedList data structure i.e. In the case of singly LinkedList, each node of Linked List contains data and pointer, which is the address of next Linked List and the last element of Singly Linked List points towards the null. Since in order to find middle element of Linked List you need to find the length of linked list, which is counting elements till end i.e. until you find the last element of Linked List.
What makes this data structure Interview question interesting is that you need to find the middle element of inkedList
in one pass and you don’t know the length of LinkedList.
This is where candidates logical ability puts into the test, whether he is familiar with space and time trade-off or not etc.
As if you think carefully you can solve this problem by using two pointers as mentioned in my last post onHow to find the length of the Singly Linked List in Java.
By using two pointers, incrementing one at each iteration and other at every second iteration. When the first pointer will point at end of Linked List, the second pointer will be pointing at a middle node of Linked List.
In fact, this two pointer approach can solve multiple similar problems like
how to find the third node from last in a Linked List in one Iteration or how to find an Nth element from last in a Linked List. In this Java programming tutorial, we will see a Java program which finds the middle element of Linked List in one Iteration.
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 withjava.util.LinkedList which is a popular Collection class in Java.
In this Java program, our class LinkedList represent a linked list data structure which contains a collection of the node and has 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 middle element of linked list in one pass in Java.
Java Program to Find the Middle Node of a Linked list in a Single-pass
001 002 003 004 005 006 007 008 009 010 011 012 013 014 015 016 017 018 019 020 021 022 023 024 025 026 027 028 029 030 031 032 033 034 035 036 037 038 039 040 041 042 043 044 045 046 047 048 049 050 051 052 053 054 055 056 057 058 059 060 061 062 063 064 065 066 067 068 069 070 071 072 073 074 075 076 077 078 079 080 081 082 083 084 085 086 087 088 089 090 091 092 093 094 095 096 097 098 099 100 101 102 | 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: 4middle element of LinkedList: 2 |
That’s all onHow to find 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 middle node of LinkedList can be used to find the 3rd element from Last or
nth element from last in a LinkedList as well.
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 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 is a Palindrome or 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 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 middle element of 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 with your friends and colleagues. If you have any question or feedback then please drop a comment.
Published on Java Code Geeks with permission by Javin Paul, partner at our JCG program. See the original article here: How to Find Middle Element of Linked List in Java in Single Pass Opinions expressed by Java Code Geeks contributors are their own. |
Website for developers and fails so bad to display code snippets on mobile browser. Great job!