Problem Given the head of a doubly linked list, reverse the linked list in place. After reversing, the head should point to the last node of the original list, and all next and prev pointers should be adjusted accordingly. Examples: Example 1: --- title: Input --- graph LR A1[1] <--> B2[2] <--> C3[3] <--> D4[4] <--> E5[5] ...
Problem Given a linked list, swap every kth node in that. If at the end of the list remaining nodes are less than k, leave them untouched. Input: A linked list, A number k. Examples Example 1: --- title: Input List with k = 4 --- graph LR A1[1] --> B2[2] --> C3[3] --> D4[4]:::kth_node --> E5[5] --> F6[6] --> G7[7] --> H8[8]:::kth_node --> I9[9] --> J10[10] classDef kth_node fill:#FFA500,stroke:#000,stroke-width:2px; ...
Problem Given a binary search tree, design an algorithm which creates a linked list of all the nodes at each depth (i.e., if you have a tree with depth D, you’ll have D linked lists) Examples Example 1: Input: 1 / \ 2 3 / \ / \ 4 5 6 7 Output: (1) => NULL (2) => (3) => NULL (4) => (5) => (6) => (7) => NULL ...
Floyd’s Cycle-Finding Algorithm Basic Algo Floyd Cycle Algorithm states that: Traverse linked list using two pointers. Move one pointer(slow_p or tortoise or walker) by one and another pointer(fast_p or hare or runner) by two. If these pointers meet at the same node then there is a loop. If pointers do not meet then linked list doesn’t have a loop. This is also called tortoise and hare approach. ...
Problem Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list. k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is. You may not alter the values in the list’s nodes, only nodes themselves may be changed. ...
Problem Given head, the head of a linked list, determine if the linked list has a cycle in it. Return true if there is a cycle in the linked list. Otherwise, return false. Examples Example 1 Input: head = [0, 1, 3, 2, 4] output: true Explanation: Cycle starts at node 2 ...
Problem Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive. There is only one repeated number in nums, return this repeated number. You must solve the problem without modifying the array nums and uses only constant extra space. OR You are given an array of length n + 1 whose elements belong to the set {1, 2, ..., n}. By the pigeonhole principle, there must be a duplicate. Find it in linear time and space. ...
Problem An XOR linked list is a more memory efficient doubly linked list. Instead of each node holding next and prev fields, it holds a field named both, which is an XOR of the next node and the previous node. Implement an XOR linked list; it has an add(element) which adds the element to the end, and a get(index) which returns the node at index. If using a language that has no pointers (such as Python), you can assume you have access to get_pointer and dereference_pointer functions that converts between nodes and memory addresses. ...
Problem Given the head of a sorted singly linked list and a target value, implement a function to find the target value using a binary search approach. If the target is found in the linked list, return the node; otherwise, return None. Examples Example 1: Input: head = [1, 3, 5, 7, 9, 11], target = 7 Output: Node with value 7 Explanation: The target 7 is found in the linked list. ...
Problem Given two sorted Linked Lists, how to merge them into the third list in sorted order? Example Example 1: Input: list1 = [1,2,4], list2 = [1,3,4] Output: [1,1,2,3,4,4] Merged List: 1 -> 1 -> 2 -> 3 -> 4 -> 4 ...