Tagged
• Algorithm
• Two Pointer Technique
•

# Introduction

Two Pointers technique is mainly used to search for data in a given data structure. This optimization technique helps to solve the problem efficiently and effectively in terms of both time and space complexities.

In this technique two pointers scan over data structure simultaneously to find the desired elements in the data structure. This technique is mainly used on data structures like arrays, linked lists, queues, strings etc.

# Middle of the Linked List

Let us understand the concept of two pointer technique using simple problem "Find middle of the linked list"

```1Problem Description :2Given a singly linked list A, find the middle element of the linked list.3
4NOTE : 51) You are given only head node of the linked list62) Length of the linked list is not known73) If there are even nodes in the linked list, there would be two middle nodes,in this case return the second middle element.8
9
13Output:14Return middle of the linked list.```

```1Example 1 :2
3  Input : 5 -> 7 -> 3 -> 10 -> 174
5  Output: 36
7  Explanation : The middle element of the linked list is 3```

```1Example 2 :2
3  Input : 15 -> 4 -> 7 -> 34
5  Output: 76  7  Explanation : As the linked list has even number of nodes, both 4 and 7 are middle elements of the linked list, In this case we return second middle element which is 7.```

# Solution Approaches

• By finding the length of the Linked List
• Using Two Pointer Technique

# Using Number of Nodes

## Algorithm

`1Step 1: Find length (len) of the linked list by traversing nodes from head 2Step 2: Now iterate the linked list len/2 times3Step 3: return len/2 node as output`

## Implementation

```1public class MiddleOfTheLinkedList {2
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
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 length of the linked list
• Space Complexity: O(1)

# Two Pointer Technique

## Algorithm

`1Step 1 : Initialize two pointers slow and fast at head of the linked list2Step 2 : Traverse over the linked list by stepping fast pointer by 2 steps and slow pointer by 1 step a head until fast pointer reached the end of the linked list3Step 3 : return slow pointer (Here slow pointer is at n/2 position of the linked list as every time fast pointer stepping ahead 2 times) `

## Implementation

```1public class MiddleOfTheLinkedListUsingTwoPointerTechnique {2
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) where n is the length of the linked list
• Space Complexity: O(1)

# Significance

Even though both approaches take O(n) time complexity, in approach 1 we are traversing the linked list two times, whereas in two pointer technique we do traverse the linked list one time to find the middle of the linked list. This way the two-pointer technique helps to optimize the solution effectively.

• Algorithm
• Two Pointer Technique
•
...