Problem You are given the head of a linked list. Determine if the linked list has a cycle. If a cycle is present, find the length of the cycle. If no cycle is present, return 0. We have already discussed the detection of linked list - here. Examples Example 1 Input: head = [0, 1, 3, 2, 4] output: 2 Explanation: Cycle starts at node 2 ...
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 a Linked List, Sort it using merge sort. Examples Example 1: Input: head = [4,2,1,3] Output: [1,2,3,4] Solution Method 1 - Recursive Refer merge sort - Merge Sort Algorithm. Get the pointer to middle node Split the list at the middle node Continue 1 and 2 , till list size is 1 or 2. Sort the elements in step 3 Merge the sorted list Now this involves 2 problems - Middle of the linked list Problem and Merge Two Sorted Linked Lists. To split linked list into 2, we can also use: Split Linked List into two halves fractionally given n ...
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 the head of a linked list, rotate the list to the right by k places. Examples Example 1: Input: head = [1,2,3,4,5], k = 2 Output: [4,5,1,2,3] Example 2: Input: head = [0,1,2], k = 4 Output: [2,0,1] ...
Problem Given a linked list and integer n, write an algorithm to find the nth node from the end in the linked list. Examples Example 1: Input: head=[1, 2, 8, 3, 7, 0, 4], n = 3 Output : 7 Explanation: 3rd Element from the end is : 7 1->2->8->3->7->0->4 3 2 1 <- indices from end ...
Problem Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and add. Implement the LRUCache class: LRUCache(int capacity) Initialize the LRU cache with positive size capacity. int get(int key) Return the value of the key if the key exists, otherwise return -1. void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key. The functions get and put must each run in O(1) average time complexity. ...
Problem Given a sorted linked list, delete all duplicates such that each element appear only once. Examples Example 1: Given 1->1->2, return 1->2. Input: head = [1,1,2] Output: [1,2] ...