![Amazon Prime](https://technologystrive.com/images/amazonPrime.jpg)
Middle Element of the Linked List
Problem Statement
1Problem Description :2Given a linked list of integers, return the middle element of the linked list.34NOTE :5If there are even number of nodes in the linked list (two middle nodes exists),6return the second middle node (which is (n/2)+1 th element where n is number of nodes of the linked list).78Input:9Head pointer of the linked list.1011Output:12Return the middle element of the linked list.
1Example 1 :23 Input : 7 -> 3 -> 5 -> 17 -> 21 -> 25 -> 8145 Output: 1767 Explanation : The middle element of the given linked list is 17.
1Example 2:23 Input : 7 -> 3 -> 5 -> 17 -> 21 -> 25 -> 81 -> 9045 Output: 2167 Explanation : as linked list has even number of nodes, middle nodes are 17 and 21.8 In this case second minimum is the answer which is 21.
Solution Approaches
- Naïve Method - By Finding Number of Nodes in the Linked List
- Using Two Pointer Technique
Using Number of Nodes
Prerequisite
Algorithm
12Input : Head of the linked list is given34Step 1: Initialize slow and fast pointer at head of the node.56Step 2: Traverse Linked List to find number of nodes (n) of the linked list.78Step 3: Traverse Linked List to (n/2) times to get the middle element.91011Step 2 in Detail :1213Step A : Initialize n to 0 and initialize current node at the head of the linked list.1415Step B : Increment n and move current pointer by one node ahead.1617Step C : Repeat Step B until current becomes null181920Step 3 in Detail :2122Step A : Initialize current node at the head of the linked list.2324Step B : Move the current node one step ahead n/2 times.2526Step C : Return current node (middle element of the linked list)27
Java Implementation
1public class MiddleOfTheLinkedList {23 public ListNode getMiddleNode(ListNode head) {4 // initialize current pointer to head of the linked list5 ListNode current = head;67 // initialize a variable to get length of the linked list8 int n = 0;910 // iterate through linked list to increment length11 while(current!= null){12 n++;13 current = current.next;14 }15 System.out.println("size is "+n);1617 // set current pointer to head of the linked list18 current = head;1920 // Now move current pointer n/2 times to get the middle node.21 for(int i=0;i<n/2;i++){22 current = current.next;23 }24 // return middle node of the linked list25 return current;26 }2728 // helper method to create a linked list easily29 // by giving values in the form of array30 // input : array31 // output : linked list (head node of the linked list)32 public ListNode create(int [] array) {3334 // create dummy node as first node for simplicity of the code35 ListNode head = new ListNode(0);36 ListNode current = head;3738 for(int i=0; i<array.length; i++){39 current.next = new ListNode(array[i]);40 current = current.next;41 }42 // as first node is dummy node43 // return head.next which is actual header44 return head.next;45 }4647 class ListNode {48 ListNode next;49 int val;5051 ListNode(int data) {52 this.val = data ;53 }54 }5556 // Driver method57 public static void main(String[] args){58 MiddleOfTheLinkedList obj = new MiddleOfTheLinkedList();5960 int[] input1 = {7, 3, 5, 17, 21, 25, 81};61 ListNode head = obj.create(input1);62 ListNode middle = obj.getMiddleNode(head);63 if(middle != null) {64 System.out.println(middle.val);65 }6667 int[] input2 = {7, 3, 5, 17, 21, 25, 81, 90};68 head = obj.create(input2);69 middle = obj.getMiddleNode(head);70 if(middle != null) {71 System.out.println(middle.val);72 }73 }7475}
Complexity Analysis
- Time Complexity : O(n) where n is the number of nodes of the linked list.
- Space Complexity: O(1) as we are not using any extra space.
Using Two Pointers
Prerequisite
Algorithm
1Input : Head of the linked list is given23Step 0: Initialize slow and fast pointer at head of the node.45Step 1: Traverse the linked list by moving slow pointer one step ahead and fast pointer two steps ahead at a time.67Step 2: Repeat Step1 until the fast pointer reaches the end of the list.89Here Number of moves by fast pointer = 2*(Number of moves by slow pointer),10It means when the fast pointer reaches the end of the linked list, the slow pointer will be at the middle node.
Example - Odd num of nodes
Input : 7 -> 3 -> 5 -> 17 -> 21 -> 25 -> 81
Step 1 :
Initialize slow and fast pointer at head node of the linked list.
Step 2 :
Move slow by one step => slow = slow.next
Move fast by two steps => fast = fast.next.next
Step 3 :
Repeat Step1 until the fast pointer reaches the end of the list.
Output : 17
Example - Even num of nodes
Java Implementation
1public class MiddleOfTheLinkedListUsingTwoPointerTechnique {23 public ListNode getMiddleNode(ListNode head) {4 // initialize slow and fast pointer to head of the linked list5 ListNode slow = head;6 ListNode fast = head;78 // iterate through linked list9 // move slow pointer one step ahead10 // and fast pointer to two steps ahead11 // repeat the same until fast pointer reaches end of the linked list12 while(fast != null && fast.next != null){13 System.out.println(fast.val +" "+ slow.val);14 slow = slow.next;15 fast = fast.next.next;16 }17 // return middle node of the linked list18 return slow;19 }2021 // helper method to create a linked list22 // easily by giving values in the form of array23 // input : array24 // output : linked list (head node of the linked list)25 public ListNode create(int [] array) {2627 // create dummy node as first node for simplicity of the code28 ListNode head = new ListNode(0);29 ListNode current = head;3031 for(int i=0; i<array.length; i++){32 current.next = new ListNode(array[i]);33 current = current.next;34 }35 // as first node is dummy node36 // return head.next which is actual header37 return head.next;38 }3940 // ListNode class41 class ListNode {42 ListNode next;43 int val;4445 ListNode(int data) {46 this.val = data ;47 }48 }4950 // Driver method51 public static void main(String[] args){52 MiddleOfTheLinkedListUsingTwoPointerTechnique obj =53 new MiddleOfTheLinkedListUsingTwoPointerTechnique();5455 int[] input1 = {7, 3, 5, 17, 21, 25, 81};56 ListNode head = obj.create(input1);57 ListNode middle = obj.getMiddleNode(head);58 if(middle != null) {59 System.out.println(middle.val);60 }6162 int[] input2 = {7, 3, 5, 17, 21, 25, 81, 90};63 head = obj.create(input2);64 middle = obj.getMiddleNode(head);65 if(middle != null) {66 System.out.println(middle.val);67 }68 }69}
Complexity Analysis
- Time Complexity : O(n) (n/2 operations in total has been performed).
- Space Complexity: O(1) as we are not using any extra space.
Approaches Comparison
Approach | Time Complexity | Space Complexity | Remarks |
---|---|---|---|
Naïve Approach (Using Number of Nodes) | O(n) | O(1) | Two Traversals Needed |
Using Two Pointer Technique | O(n) | O(1) | Single Traversal |