Problem 1: Largest Rectangle in Histogram

Link to the problem: https://leetcode.com/problems/largest-rectangle-in-histogram/

class Solution {
    public int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        int maxArea = 0;

        for(int i = 0; i < heights.length; i++) {
            while(stack.peek() != -1 && heights[i] <= heights[stack.peek()]) {
                int height = heights[stack.pop()];
                int width = i - stack.peek() - 1;
                maxArea = Math.max(maxArea, height * width);
            }
            stack.push(i);
        }

        while(stack.peek() != -1) {
            int height = heights[stack.pop()];
            int width = heights.length - stack.peek() - 1;
            maxArea = Math.max(maxArea, height * width);
        }

        return maxArea;
    }
}

---

Problem 2: LRU Cache

Link to the problem: https://leetcode.com/problems/lru-cache/

class LRUCache {

    LinkedList<Integer> ll;
    Map<Integer, Integer> map;
    int size;

    public LRUCache(int capacity) {
        ll = new LinkedList<>();
        map = new HashMap<>(); 
        size = capacity;
    }

    public int get(int key) {
        if(map.containsKey(key)){
            ll.remove((Integer) key);
            ll.add(key);
            return map.get(key);
        }else return -1;
    }

    public void put(int key, int value) {
        if(map.containsKey(key)){
            map.put(key, value);
            ll.remove((Integer) key);
            ll.add(key);
        }else if(ll.size()<size){
            ll.add(key);
            map.put(key, value);
        }else{
            Integer num = ll.removeFirst();
            ll.add(key);
            map.remove(num);
            map.put(key, value);
        }
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

---

Problem 3: Swap Nodes in Pairs

Link to the problem: https://leetcode.com/problems/swap-nodes-in-pairs/

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head==null || head.next==null) return head;
        ListNode ptr = new ListNode(0);
        ptr.next = head;
        ListNode curr = ptr;
        while(curr.next!=null && curr.next.next!=null) {
            ListNode first = curr.next;
            ListNode second = curr.next.next;

            curr.next = second;
            first.next = second.next;
            second.next = first;

            curr = first;
        }
        return ptr.next;
    }
}

---

Problem 4: Sort List

Link to the problem: https://leetcode.com/problems/sort-list/

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        if(head==null || head.next==null) return head;
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        while(head!=null){
            pq.add(head.val);
            head = head.next;
        }
        ListNode res = new ListNode(0);
        ListNode temp = new ListNode(pq.poll(), null);
        res.next = temp;
        while(!pq.isEmpty()){
            temp.next = new ListNode(pq.poll(), null);
            temp = temp.next;
        }
        return res.next;
    }
}

---

Problem 5: Rotate List

Link to the problem: https://leetcode.com/problems/rotate-list/

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if(head==null || head.next==null) return head;
        int size = 0;
        ListNode ptr = head;
        while(ptr!=null){
            ptr = ptr.next;
            size++;
        }
        k%=size;
        if(k==0) return head;
        k = size-k;
        ptr = head;
        while(k-->1) ptr = ptr.next;
        ListNode temp = ptr.next;
        ptr.next = null;
        ptr = head;
        head = temp;
        while(temp.next!=null) temp=temp.next;
        temp.next = ptr;
        return head;
    }
}

---