Tagged
• DSA Problems
• Linked List
• Two Pointer Technique
•

# 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 -> 814
5  Output: 176
7  Explanation : The middle element of the given linked list is 17.```

```1Example 2:2
3  Input : 7 -> 3 -> 5 -> 17 -> 21 -> 25 -> 81 -> 904
5  Output: 216
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

## Algorithm

```1
2Input : Head of the linked list is given3
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 null18
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 list5        ListNode current = head;6
7        // initialize a variable to get length of the linked list8        int n = 0;9
10        // iterate through linked list to increment length11        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 list18        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 list25        return current;26    }27
28    // 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) {33
34        // create dummy node as first node for simplicity of the code35        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 header44        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 method57    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

## Algorithm

```1Input : Head of the linked list is given2
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

## Java Implementation

```1public class MiddleOfTheLinkedListUsingTwoPointerTechnique {2
3    public ListNode getMiddleNode(ListNode head) {4        // initialize slow and fast pointer to head of the linked list5        ListNode slow = head;6        ListNode fast = head;7
8        // 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    }20
21    // 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) {26
27        // create dummy node as first node for simplicity of the code28        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 header37        return head.next;38    }39
40    // ListNode class41    class ListNode {42        ListNode next;43        int val;44
45        ListNode(int data) {46            this.val = data ;47        }48    }49
50    // Driver method51    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

ApproachTime ComplexitySpace ComplexityRemarks
Naïve Approach (Using Number of Nodes)O(n)O(1)Two Traversals Needed
Using Two Pointer TechniqueO(n)O(1)Single Traversal

• DSA Problems
• Linked List
• Two Pointer Technique
•
...