Problem Statement

1Problem Description :
2Given a linked list of integers, return the middle element of the linked list.
3
4NOTE : 
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).
7
8Input: 
9Head pointer of the linked list.
10
11Output:
12Return the middle element of the linked list.

1Example 1 :
2
3  Input : 7 -> 3 -> 5 -> 17 -> 21 -> 25 -> 81
4
5  Output: 17
6
7  Explanation : The middle element of the given linked list is 17.

1Example 2:
2
3  Input : 7 -> 3 -> 5 -> 17 -> 21 -> 25 -> 81 -> 90
4
5  Output: 21
6
7  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

• Linked List

Algorithm

1
2Input : Head of the linked list is given
3
4Step 1: Initialize slow and fast pointer at head of the node.
5
6Step 2: Traverse Linked List to find number of nodes (n) of the linked list.
7
8Step 3: Traverse Linked List to (n/2) times to get the middle element.
9
10
11Step 2 in Detail :
12
13Step A : Initialize n to 0 and initialize current node at the head of the linked list.
14
15Step B : Increment n and move current pointer by one node ahead.
16
17Step C : Repeat Step B until current becomes null
18
19
20Step 3 in Detail :
21
22Step A : Initialize current node at the head of the linked list.
23
24Step B : Move the current node one step ahead n/2 times.
25
26Step C : Return current node (middle element of the linked list)
27

Java Implementation

1public class MiddleOfTheLinkedList {
2
3    public ListNode getMiddleNode(ListNode head) {
4        // initialize current pointer to head of the linked list
5        ListNode current = head;
6
7        // initialize a variable to get length of the linked list
8        int n = 0;
9
10        // iterate through linked list to increment length
11        while(current!= null){
12            n++;
13            current = current.next;
14        }
15        System.out.println("size is "+n);
16
17        // set current pointer to head of the linked list
18        current = head;
19
20        // 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 list
25        return current;
26    }
27
28    // helper method to create a linked list easily
29    // by giving values in the form of array
30    // input : array
31    // output : linked list (head node of the linked list)
32    public ListNode create(int [] array) {
33
34        // create dummy node as first node for simplicity of the code
35        ListNode head = new ListNode(0);
36        ListNode current = head;
37
38        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 node 
43        // return head.next which is actual header
44        return head.next;
45    }
46
47    class ListNode {
48        ListNode next;
49        int val;
50
51        ListNode(int data) {
52            this.val = data ;
53        }
54    }
55
56    // Driver method
57    public static void main(String[] args){
58        MiddleOfTheLinkedList obj = new MiddleOfTheLinkedList();
59
60        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        }
66
67        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    }
74
75}

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

• Linked List
• Two Pointer Technique

Algorithm

1Input : Head of the linked list is given
2
3Step 0: Initialize slow and fast pointer at head of the node.
4
5Step 1: Traverse the linked list by moving slow pointer one step ahead and fast pointer two steps ahead at a time.
6
7Step 2: Repeat Step1 until the fast pointer reaches the end of the list. 
8
9Here 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 {
2
3    public ListNode getMiddleNode(ListNode head) {
4        // initialize slow and fast pointer to head of the linked list
5        ListNode slow = head;
6        ListNode fast = head;
7
8        // iterate through linked list
9        // move slow pointer one step ahead
10        // and fast pointer to two steps ahead
11        // repeat the same until fast pointer reaches end of the linked list
12        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 list
18        return slow;
19    }
20
21    // helper method to create a linked list
22    // easily by giving values in the form of array
23    // input : array
24    // output : linked list (head node of the linked list)
25    public ListNode create(int [] array) {
26
27        // create dummy node as first node for simplicity of the code
28        ListNode head = new ListNode(0);
29        ListNode current = head;
30
31        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 node 
36        // return head.next which is actual header
37        return head.next;
38    }
39
40    // ListNode class
41    class ListNode {
42        ListNode next;
43        int val;
44
45        ListNode(int data) {
46            this.val = data ;
47        }
48    }
49
50    // Driver method
51    public static void main(String[] args){
52        MiddleOfTheLinkedListUsingTwoPointerTechnique obj = 
53        new MiddleOfTheLinkedListUsingTwoPointerTechnique();
54
55        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        }
61
62        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