Intuition

The problem is to identify the middle element or node of the given Singly Linked List and return second middle element if the length of List is even. Basically there are two approaches to solve this problem:

• Approach 1: Brute Force $$$TC:O(N) + O(N/2)$$$
• Approach 2: Tortoise Rabbit Algorithm $$$TC:O(N/2)$$$

Approach 1

In the Brute Force approach, we will be calculating the length of Linked List by traversing through each element using temp pointer. Then calculate the half of length ($$$length/2$$$). Once again traverse through the Linked List and move the head variable until half of its length is reached, after reaching return the head pointer. Now the head pointer contains the chain from middle element of that List.

• Time complexity: O(N) + O(N/2)
• Space complexity: O(K)

Code

struct ListNode* middleNode(struct ListNode* head){
    struct ListNode* ptr = head;
    int length=0;
    int mid;

    while(ptr != NULL){
        ptr = ptr->next;
        length++;
    }

    mid = length/2;
    while(mid--){
            head = head->next;
    }

    return head;
}

Result

Runtime: 2ms Memory: 6MB

Approach 2

By using Tortoise Rabbit Algorithm, initially we assign two pointers tortoise and rabbit to head node. Now, we move both the pointers in such a way that Tortoise pointer moves one step forward asusual and Rabbit pointer moves two steps forward. So, when the Rabbit pointer reaches the end of List or the last node of List we have Tortoise pointer at the middle node of the List. Then we return the Tortoise pointer which contains the chain from middle element of the List.

• Time complexity: O(N/2)
• Space complexity: O(K)

Code

// In C
struct ListNode* middleNode(struct ListNode* head){
    struct ListNode *tortoise = head;
    struct ListNode *rabbit = head;

    while(rabbit != NULL && rabbit->next != NULL){
        tortoise = tortoise->next;
        rabbit = rabbit->next->next;
    }

    return tortoise;
}

// In Java
class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode tortoise = head;
        ListNode rabbit = head;

        while(rabbit != null && rabbit.next != null){
            tortoise = tortoise.next;
            rabbit = rabbit.next.next;
        }

        return tortoise;
    }
}

Result

Runtime: 0ms Memory: 6MB

Upvote the solution, if you like the appraoch!

Intuition

The Reverse Polish Notation is nothing but Postfix expression, where operands are followed by operands in an expression. In a valid postfix expression, whenever an operator is encountered two leading operands are evaluated with the operator and the result is replaced in the expression.

Approach

Here, I have used Monotonic Stack to evaluate the postfix expression. The logic is simple:

Iterate through the expression linearly If a number is encountered, push into the stack If an operator is encountered, pop the top elements from stack and assign the topmost number as RHS and the previous number as LHS Evaluate the expression based on the operator (+, — ,* , /) and push the result into stack Repeat the same process, until the expression is completely traversed. At the end return stack[0] which is the final result after evaluating all the numbers in the expression.

Complexity

Time complexity: O(N)

Space complexity: O(k)

Code

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        if (len(tokens) == 1):
            return int(tokens[0])

        stack = []
        top = -1
        operators = "+-*/"

        for ele in tokens:
            if (ele in operators):
                rhs = int(stack.pop())
                lhs = int(stack.pop())
                res = 0
                if (ele == "+"):
                    res = lhs+rhs
                elif (ele == "-"):
                    res = lhs-rhs
                elif (ele == "*"):
                    res = lhs*rhs
                elif (ele == "/"):
                    res = int(lhs/rhs)
                stack.append(res)
            else:
                top += 1
                stack.append(ele)
        
        return stack[0]