How do you find middle element of LinkedList in one pass is a programming
question often asked to Java and non Java programmers in telephonic Interview.
This question is similar to checking
palindrome or calculating
factorial, where Interviewer some time also ask to write code. In order to answer this question candidate must be familiar with LinkedList data structure
i.e. In case of singly LinkedList, each node of Linked List contains data and
pointer, which is address of next Linked List and last element of Singly Linked
List points towards null. Since in order to find middle element of Linked List
you need to find length of LinkedList, which is counting elements till end i.e.
until you find the last element on Linked List. What makes this data structure
Interview question interesting is that you need to find middle element of LinkedList in one pass and you don’t know length
of LinkedList. This is where candidates logical ability puts into 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 on How
to find length of Singly Linked List in Java. By using two pointers,
incrementing one at each iteration and other at every second iteration. When
first pointer will point at end of Linked List, second pointer will be pointing
at middle node of Linked List. In fact
this two pointer approach can solve multiple similar problems e.g. How to find
3rd element from last in a Linked List in one Iteration or How to
find nth element from last in a Linked List. In this Java programming tutorial
we will see a Java program which finds middle element of Linked List in one
Iteration.
Java program to find middle element of
LinkedList in one pass
Here is complete Java program to find 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
which is a popular Collection class
in Java. In this Java program, our class LinkedList represent a linked list
data structure which contains collection of node and has head and tail. Each Node
contains data and address part. 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.
import test.LinkedList.Node;
/**
* Java program to find middle element of linked list in one pass.
* In order to find middle element of linked list we need to find length
first
* but since we can only traverse linked list one time, we will use two
pointers
* one which we will increment on each iteration while other which will be
* incremented every second iteration. so when first pointer will point to
the
* end of linked list, second will be pointing to the middle element of
linked list
* @author
*/
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
middle element of LinkedList : 2
That’s all on How 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 technique mentioned here to find middle node of LinkedList
can be used to find 3rd element from Last
or nth element from last in a LinkedList as well.
Other Java programming tutorials from Javarevisited blog
Source:http://javarevisited.blogspot.com/2012/12/how-to-find-middle-element-of-linked-list-one-pass.html
Tidak ada komentar:
Posting Komentar