In this tutorial, Let’s discuss how to find middle element of a linked list in a single traversal.
Given a singly linked list, write a code to find middle element in a linked list.
For example: Given a linked list, the middle element in this linked list is 8.
15 -> 9 -> 8 -> 5 -> 6 -> NULL
This type of questions are generally asked in an interviews.
There are multiple approaches to solve this problem. In this tutorial, I am going to discuss two approaches through which we can find the middle element of a singly linked list in one pass.
I have also added video tutorial at the end of this post.
How to Find Middle Element of a Linked List?
Method 1: Finding middle element of a linked in two traversal
i) Traverse a linked list and find the length of a linked list.
ii) Once we know the length of a linked list. We can traverse again upto length/2 and print the value of a node present at mid position.
By using this method we can solve this problem in two traversal.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
//Find middle element in linked list using two traversal public ListNode middleNode(ListNode head) { int len =0; ListNode temp = head; //Find length of a linked list while (temp !=null){ temp = temp.next; len++; } //Intialized, again with head pointer temp = head; int mid = 0; while (mid < len/2){ temp = temp.next; mid++; } return temp; } |
Can we do better than that? How do you find the middle element in a singly linked list in one pass?
Yes we can solve this problem in a single traversal. Let’s discuss our second approach.
Check if a linked list is palindrome or not
Sort a linked list of 0s, 1s and 2s
Method 2: Find middle element in linked list in one pass using two pointers.
i) Use two pointer slow and fast. Initialized both the pointers to the head of a linked list.
ii) Move fast pointer by two step and slow pointer by one step in each iteration.
iii) When fast pointer reaches at the end of a linked list, The slow pointer points to the middle element of a linked list.
Programming questions on linked list
Find Middle Element of a Linked List
Find Middle Element of a Linked List in a Single Traversal – Java Code
We have already discussed the algorithm for finding middle element in a linked list.
Let’s write it’s java code.
|
1 2 3 4 5 6 7 8 9 10 11 12 |
//Node class which has two attributes public class Node { int data; Node next; public Node(int data) { this.data = data; this.next = null; } } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 |
/** * Main class */ public class MiddleElement { private Node head; //In constructor, Initialize head attribute to null public MiddleElement() { this.head = null; } public Node insert(int data) { if (head == null) { head = new Node(data); } else { // Create a new node Node temp = new Node(data); // New node points to head temp.next = head; // Head points to a new node head = temp; } return head; } //Logic to print middle element of a linked list public void printMiddleElement() { Node slow = head; Node fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } System.out.println(" Middle Element of a Linked List is " + slow.data); } public void print() { Node temp = head; /* * Traverse a list and check if it not points to null. If it points to * null, It means there is no node present after that and we need to end * the loop. */ while (temp != null) { System.out.println(temp.data); temp = temp.next; } } public static void main(String[] args) { MiddleElement ll = new MiddleElement(); ll.insert(6); ll.insert(5); ll.insert(8); ll.insert(9); ll.insert(15); ll.print(); ll.printMiddleElement(); } } |
Find Middle Element in a Linked List LeetCode Solution
Let’s discuss the solution of Middle of the Linked List LeetCode Problem.
In this example, We have solved this problem using two pointers in a single pass.
The time complexity is O(n) and it’s space complexity is O(1).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
//Middle of the Linked List LeetCode Solution public ListNode middleNode(ListNode head) { /* Declare two pointers and initialized with head. */ ListNode slow = head; ListNode fast = head; //Move fast pointers by 2 step and slow by 1 while(fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } return slow; } |
