Solution 1(Two iteration of list) - Find the length of linked list and traverse again from beginning of list up to half of the linked list(as described above). It is not an efficient approach, because of two iteration.
Solution 2(One iteration of list) - Use two reference, one fast reference and another one slower one. Fast reference moves with twice speed as slow reference. Traverse the linked list with both and the moment fast reference reaches at end of list , slow reference will be at middle of list.
Below is sample code which uses two references and find middle element of list(fast references - 2x and slow references - x):-
private Node findMiddleElement(Node head) { |
Below is complete sample program for finding middle of linked list-
package com.devinline.linkedlist;
public class FindMiddleElementOflInkedList {
private Node findMiddleElement(Node head) {
Node fast2Xreference = head;
Node slowXRefernce = head;
/* Loop until fast2xReference reaches end of list or last node */
while (fast2Xreference != null && fast2Xreference.next != null) {
slowXRefernce = slowXRefernce.next;
/* check whether, fast reference can go to next to next node */
if (fast2Xreference.next != null)
fast2Xreference = fast2Xreference.next.next;
}
return slowXRefernce;
}
class Node {
public int data;
public Node next; // reference(handler) for next Node.
public Node(int data) {
this.data = data;
this.next = null;
}
}
public static void main(String[] args) {
Node head1;
Node head2;
/* First linked list formation - odd number of elements */
FindMiddleElementOflInkedList fml = new FindMiddleElementOflInkedList();
Node node1 = fml.new Node(12);
head1 = node1;
Node node2 = fml.new Node(18);
Node node3 = fml.new Node(172);
Node node4 = fml.new Node(62);
head1.next = node2;
head1.next.next = node3;
head1.next.next.next = node4;
System.out.println("Even number of elements:- "
+ "Middle element of linked list [12 18 172 62] is "
+ +fml.findMiddleElement(head1).data);
/* Second linked list formation - Even number of elements */
FindMiddleElementOflInkedList fm2 = new FindMiddleElementOflInkedList();
Node node12 = fm2.new Node(121);
head2 = node12;
Node node22 = fm2.new Node(8);
Node node32 = fm2.new Node(72);
Node node42 = fm2.new Node(162);
Node node52 = fm2.new Node(32);
Node node62 = fm2.new Node(245);
head2.next = node22;
head2.next.next = node32;
head2.next.next.next = node42;
head2.next.next.next.next = node52;
head2.next.next.next.next.next = node62;
System.out.println("Odd number of elements:- "
+ "Middle element of linked list [8 72 162 32 245] is "
+ fml.findMiddleElement(head2).data);
}
}
Even number of elements:- Middle element of linked list [12 18 172 62] is 172
Odd number of elements:- Middle element of linked list [8 72 162 32 245] is 162
========================================
Another linked list problems which uses fast and slow references :-
1. To check, linked list has even or odd number of elements.
0 comments:
Post a Comment