Prev   Next

Mid of Linked List







The goal isn't to live forever, the goal is to create something that will.
~ Chuck Palahniuk

Mid of Linked List

Hey coder. We are going to discuss the question "Mid of Linked List" in this article.

We suggest you go through the problem statement and watch the question video first if you haven't already.

Important Links :Problem link, Question Video, Solution Video

Problem Discussion :

The problem states that:

  • The function should be an iterative function and should return the middle of the linked list.
  • make sure to not use size data member directly or indirectly (by calculating size via making a traversal)
  • In the linked list of even size, consider the end of the first half as mid.

Constraints:

  • Size property should not be used directly or indirectly.
  • Constant time, single traversal is expected.
  • Iterative solution, (not recursion) is expected.
img

Figure 1 depicts the mid node for an odd and an even linked list.

The strategy for this question is the Two Pointer Approach.

Approach :

In this approach we initially put two pointers: s (slow) and f (fast) at the head of the given linked list as shown in figure 2.

img

For every 1 step of s pointer, the f pointer moves 2 steps (see figure 3).

img

This means that the speed of the 'f' pointer is twice that of the 's' pointer. So when the f pointer reaches the end, then the s pointer would be at the mid of the linked list (figure 4).

img

Hence, when 'f' points at the end node, then the node at the 's' pointer is the mid.

Meditate on the fact that 'f' pointing at the last node can be described as f.next=null which means that the position of f pointer when there is no node after it.

We have learnt the algorithm for this question, now let's code it quickly.

import java.io.*; import java.util.*; public int mid(){ Node s=head; Node f=head; while(f.next!=null && f.next.next!=null) { s=s.next; f=f.next.next; } return s.data; }
java; true";
CODE DISCUSSION

In the while loop you must have noticed one more condition : f.next.next!=null.

Why do you think it is for?

Reader, it's for the even cases.

Let's see how by first only checking the condition f.next!=null for a linked list of even size (see figure 5).

img

In figure 5(B) you can see that s pointer is at the desired mid location but since f.next is still not null, therefore the loop iterates again and s pointer has to move 1 more step at a position which is not the mid position.

Hence, we check the condition f.next.next!=null , so that we move the f piece only when at least 2 nodes are present further.

Analysis:
Time Complexity:

O(n)

The time complexity is linear as a while loop is used in the program.

Space Complexity:

O(1)

Since no extra space is used, therefore the space complexity is constant.

You should also check out the solution video for this question.

Linked lists
Author: Shreeya Gupta
 
Run
Id Name