Mid Of Linked List

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

1. You are given a partially written LinkedList class.
2. Here is a list of existing functions:
2.1 addLast - adds a new element with given value to the end of Linked List
2.2. display - Prints the elements of linked list from front to end in a single line.
All elements are separated by space
2.3. size - Returns the number of elements in the linked list.
2.4. removeFirst - Removes the first element from Linked List.
2.5. getFirst - Returns the data of first element.
2.6. getLast - Returns the data of last element.
2.7. getAt - Returns the data of element available at the index passed.
2.8. addFirst - adds a new element with given value in front of linked list.
2.9. addAt - adds a new element at a given index.
2.10. removeLast - removes the last element of linked list.
2.11. removeAt - remove an element at a given index
2.12 kthFromLast - return kth node from end of linked list.
3. You are required to complete the body of mid function. The function should be an iterative function and should return the mid of linked list. Also, make sure to not use size data member directly or indirectly (by calculating size via making a traversal). In linked list of odd size, mid is unambigous. In linked list of even size, consider end of first half as mid.
4. Input and Output is managed for you.
Input Format
Input is managed for you
Output Format
Output is managed for you
Question Video
Constraints
1. Size property should not be used directly or indirectly
2. Constant time, single traversal is expected
3. Iterative solution, (not recursion) is expected.
Sample Input
addLast 10
getFirst
addLast 20
addLast 30
getFirst
getLast
getAt 1
addLast 40
mid
getLast
addLast 50
removeFirst
getFirst
removeFirst
removeFirst
mid
removeFirst
removeFirst
getFirst
quit
Sample Output
10
10
30
20
20
40
20
40
List is empty


  • Editorial

    The problem here deals with implementing the mid() function which returns the data present at the middlemost node of the list.

    We are given a linked list class which has three data members:

    1. Head: It points to the starting node of the linked list.

    2. Tail: It points to the last node of the linked list.

    3. Size: It stores the current length (or size) of the linked list.

    There can be two cases for the problem:

    1. Length of List is Even

    Input List: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8

    Output: 4

    2. Length of List is Odd

    Input List: 1 -> 2 -> 3 -> 4 -> 5

    Output: 3

    To solve this problem we would be taking a two-pointer approach (In this particular case also known as Hare and Tortoise Approach) wherein we take two pointers a fast and a slow pointer where the fast pointer jumps at double the speed of the slow pointer, the intuition behind this is that if fast and slow have to cover the same length of list say n then if the speed of fast is twice the speed of slow which would imply that when fast reaches the end of the list then slow would be exactly at the middle of the list, hence data at slow pointer would be our result. This approach is also known as Hare and Tortoise approach as here fast pointer acts as a hare and slow pointer acts like a tortoise, hence the name.

    Below is the implementation in Java:

    public int mid(){
                                        Node f = head;
                                        Node s = head; 
                                        while(f.next != null && f.next.next != null){
                                        f = f.next.next;
                                        s = s.next;
                                        } 
                                        return s.data;
                                    }

    java false

    Dry Run Case 1 (Even Length)

    Input List: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8

    Output: 4

    Initially, slow = 1st Node and fast = 1st Node

    1. First Iteration

    fast.next = 2nd Node != null&&fast.next.next = 3rd Node != null

    fast = fast.next.next = 3rd Node

    slow = slow.next = 2nd Node

    2. Second Iteration

    fast.next = 4thNode != null&&fast.next.next = 5thNode != null

    fast = fast.next.next = 5thNode

    slow = slow.next = 3rdNode

    3. Third Iteration

    fast.next = 6thNode != null&&fast.next.next = 7thNode != null

    fast = fast.next.next = 7thNode

    slow = slow.next = 4thNode

    4. Fourth Iteration

    fast.next = 8th Node != null&&fast.next.next == null

    Loop Breaks

    Returnslow.data = 4 (Result)

    Dry Run Case 2 (Odd Length)

    Input List: 1 -> 2 -> 3 -> 4 -> 5

    Output: 3

    Initially, slow = 1st Node and fast = 1st Node

    1. First Iteration

    fast.next = 2nd Node != null&&fast.next.next = 3rd Node != null

    fast = fast.next.next = 3rd Node

    slow = slow.next = 2nd Node

    2. Second Iteration

    fast.next = 4th Node != null&&fast.next.next = 5th Node != null

    fast = fast.next.next = 5th Node

    slow = slow.next = 3rd Node

    3. Third Iteration

    fast.next = 6thNode == null

    Loop Breaks

    Returnslow.data = 3 (Result)

    Time Complexity: O(n)

    The time complexity for the function is linear as the traversal of the linked list is involved.

    Space Complexity: O(1)

    The space complexity for the function is constant as we have only used referenced variables in our algorithm.

  • Asked in Companies
  • Related Topics






Video Solution

Code Solution

Run
 
Run
Id Name