Question: In given a Linked List, find the middle of the list and print the number.
Input : -> 4-> 2-> 7-> 9-> 1
Output : 7
Before starting you have to must know about Linked list and how to create it and Inserting node (data) in LinkedList.
There is many approach to find middle number in LinkedList.
1. Single pointer approach
In this approach, we will scan the entire list and count the number of nodes. We divide the number by 2 and then again traverse the list up to that node.
package in.eyehunt.data.struc;
public class LinkedList {
Node head; // head of list
// Linked list Node.
class Node {
int data;
Node next;
// Parameterized constructor
Node(int d) {
data = d;
next = null;
}
}
void push(int n) {
//create new node
Node newNode = new Node(n);
// next node is head
newNode.next = head;
// move had point to new node
head = newNode;
}
void findMiddleNode() {
if (head == null) {
System.out.println("LinkedList is null");
} else {
int middleNode = (count() % 2 == 0) ? (count() / 2) : ((count() + 1) / 2);
Node pointerNode = head;
int countNodes = 0;
while (countNodes != middleNode -1) {
pointerNode = pointerNode.next;
countNodes ++;
}
System.out.println("\nMiddle node of linked List is " + middleNode);
System.out.println("Middle node data is " + pointerNode.data);
}
}
//Returns count of nodes in linked list (iteration)
public int count() {
int a = 0;
Node n = head;
while (n != null) {
n = n.next;
a++;
}
return a;
}
void printAllNodes() {
Node node = head;
while (node != null) {
System.out.print("-> " + node.data);
node = node.next;
}
}
public static void main(String a[]) {
//create a simple linked list with 4 nodes
LinkedList linkedList = new LinkedList();
linkedList.push(1);
linkedList.push(9);
linkedList.push(7);
linkedList.push(2);
linkedList.push(4);
linkedList.printAllNodes();
linkedList.findMiddleNode();
}
}Output : -> 4-> 2-> 7-> 9-> 1
Middle node of linked List is 3
Middle node data is 7
Time Complexity: Time for finding the length of list + Time for locating middle node = O(n) + O(n) ≈ O(n)Space Complexity: O(1)
2. Using 2 pointers
With 2 pointers to traverse the list ,we can find the middle of list with only one scan on the Linked List.
- pointer1 travels one node at a time
- pointe2 travels two nodes a time.
Thus, when pointe2 reaches the end of the Linked List, pointer1 will point at the middle of the Linked List.
package in.eyehunt.data.struc;
public class LinkedList {
Node head; // head of list
// Linked list Node.
class Node {
int data;
Node next;
// Parameterized constructor
Node(int d) {
data = d;
next = null;
}
}
void push(int n) {
//create new node
Node newNode = new Node(n);
// next node is head
newNode.next = head;
// move had point to new node
head = newNode;
}
void findMiddleNode() {
if (head == null) {
System.out.println("LinkedList is null");
} else {
Node pointer1 = head;
Node pointer2 = head;
while (pointer2 != null && pointer2.next != null) {
pointer1 = pointer1.next;
pointer2 = pointer2.next.next;
}
System.out.println("\nMiddle node data is " + pointer1.data);
}
}
void printAllNodes() {
Node node = head;
while (node != null) {
System.out.print("-> " + node.data);
node = node.next;
}
}
public static void main(String a[]) {
//create a simple linked list with 4 nodes
LinkedList linkedList = new LinkedList();
linkedList.push(1);
linkedList.push(9);
linkedList.push(7);
linkedList.push(2);
linkedList.push(4);
linkedList.printAllNodes();
linkedList.findMiddleNode();
}
}Output: -> 4-> 2-> 7-> 9-> 1
Middle node data is 7
Time Complexity: O(n)Space Complexity: O(1)
here is more LinkedList interview questions :