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

To learn about linked list data structure, visit Linked List Tutorial.

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 list
62) Length of the linked list is not known
73) 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
10Input: 
11A pointer to the head of the linked list.
12
13Output:
14Return middle of the linked list.

1Example 1 :
2
3  Input : 5 -> 7 -> 3 -> 10 -> 17
4
5  Output: 3
6
7  Explanation : The middle element of the linked list is 3

1Example 2 :
2
3  Input : 15 -> 4 -> 7 -> 3
4
5  Output: 7
6  
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 times
3Step 3: return len/2 node as output

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 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 list
2Step 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 list
3Step 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
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) 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.