Problem Given a circular linked list, implement an algorithm which returns node at the beginning of the loop. If there is no cycle, return null. Try solving it using constant additional space. Definition - Circular Linked List A (corrupt) linked list in which a node’s next pointer points to an earlier node, so as to make a loop in the linked list. This is extension of Linked List Cycle 1 - Detect Cycle ...
Problem Given the head of a singly linked list, return the middle node of the linked list. If there are two middle nodes, return the second middle node. Example 1: graph LR 1 --> 2 --> 3:::RedNode --> 4 --> 5 classDef RedNode fill:#ff0000; Input: head = [1,2,3,4,5] Output: [3,4,5] Explanation: The middle node of the list is node 3. ...
Problem Given the head of a singly linked list, sort the list using insertion sort, and return the sorted list’s head. The steps of the insertion sort algorithm: Insertion sort iterates, consuming one input element each repetition and growing a sorted output list. At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list and inserts it there. It repeats until no input elements remain. The following is a graphical example of the insertion sort algorithm. ...
Problem You are given the head of a singly linked-list. The list can be represented as: $$ L_0 → L_1 → … → L_{n - 1} → L_n $$ Reorder the list to be on the following form:: $$ L_0 → L_n → L1 → L_{n - 1} → L2 → L_{n - 2} → … $$ Examples Example 1: --- title: Input List --- graph LR A1[1] --> B2[2] --> C3[3] --> D4[4] ...
Problem Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum. Examples Example 1: graph TD; A[5] --> B[4] & C[8] B --> D[11] & E[null] C --> F[13] & G[4] D --> H[7] & I[2] G --> L[5] & M[1] style A fill:#f9f style B fill:#f9f style C fill:#f9f style D fill:#f9f style I fill:#f9f style G fill:#f9f style L fill:#f9f ...
Recover Binary Search Tree Problem Problem You are given the root of a binary search tree (BST), where the values of exactly two nodes of the tree were swapped by mistake. Recover the tree without changing its structure. Note: A solution using O(n) space is pretty straight forward. Could you devise a constant space solution? Example Example 1: Input: *1 / *3 \ 2 Output: *3 / *1 \ 2 ...
Problem Given a positive integer n, generate an n x n matrix filled with elements from 1 to n2 in spiral order. Examples Example 1: Input: n = 3 Output: [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ] Example 2: Input: n = 4 Output: [ [1, 2, 3, 4], [12, 13, 14, 5], [11, 16, 15, 6], [10, 9, 8, 7] ] ...
Problem Given an unsorted integer array, find the first missing positive integer. Follow up You have to find the smallest positive number missing from the array in O(n) time using constant extra space. You can modify the original array. Examples Example 1: Input: nums = [1,2,0] Output: 3 ...
Problem Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., [0, 1, 2, 4, 5, 6, 7] might become [4, 5, 6, 7, 0, 1, 2]). You are given a target value to search. If found in the array return its index, otherwise return -1. You may assume no duplicate exists in the array. Follow up: what if duplicates are allowed? ...
Problem Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution. Examples Example 1: Input: nums = [-1,2,1,-4], target = 1 Output: 2 Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2). ...