Given a singly linked list, determine if its a palindrome. Return 1 or 0 denoting if its a palindrome or not, respectively. Notes: – Expected solution is linear in time and constant in space. For example, List 1–>2–>1 is a palindrome. List 1–>2–>3 is not a palindrome. Solution: This method takes O(n) time and O(1) … Read More →
Flatten A Binary Tree to Linked List (In-place)
Problem: Given a binary tree, flatten it to a linked list in-place. For example, The flattened tree should look like: Solution: We can solve this problem recursively by doing a in-order traversal of the tree. Implementation:(Recursion) Non-Recursion, No Stack We can also solve the problem even without a stack: Each time when we prune a … Read More →
Union and Intersection of two Linked Lists
Given two Linked Lists, create union and intersection lists that contain union and intersection of the elements present in the given lists. Order of elments in output lists doesn’t matter. Following are simple algorithms to get union and intersection lists respectively. Intersection (list1, list2) Initialize result list as NULL. Traverse list1 and look for its … Read More →
Implement Stack and Queue using Linked List in Java
The implementation of a linked list is pretty simple in Java. Each node has a value and a link to next node. Two popular applications of linked list are stack and queue. Stack: What is stack? Stack is a linear data structure which implements data on last in first out criteria. Here is a java … Read More →
Sort a Linked List of 0s, 1s and 2s
Given a Singly linked list with each node containing either 0, 1 or 2. Write code to sort the list. Input : 1 -> 1 -> 2 -> 0 -> 2 -> 0 -> 1 -> 0 Output : 0 -> 0 -> 0 -> 1 -> 1 -> 1 -> 2 -> 2 Solution: … Read More →
Repeatedly Delete N nodes after M nodes of a Linked list
Given a linked list and two integers M and N. Traverse the linked list such that you retain M nodes then delete next N nodes, continue the same until end of the linked list. Input: M = 2, N = 2 Linked List: 1->2->3->4->5->6->7->8 Output: Linked List: 1->2->5->6 The main part of the problem is … Read More →
Print Linked List Elements in Reverse order
Write a program to print elements of a linked list in reverse order by using same single linked list. Solution: We can solve this problem without actually reversing the linked list. Using recursion we have given the below solution. This implementation will be internally using stack to store each recursive function call. Complexity: O(N), where … Read More →
Remove Duplicates from a Linked List
Given an unsorted linked list, and without using a temporary buffer, write a method that will delete any duplicates from the linked list. Implemntation: Complexity: O(n^2) If you can sort the list in O(nlogn) then it will take O(nlogn). Post your solution in comments.
Reverse a Linked List using Recursion
Problem: To test both data structure and the recursion concept, a wonderful and confusing interview question asked to experienced people is “Reverse a linked list using recursion”. Solution: In recursive approach, we need to move to the end of the node. But must stop just before the end of the node, and we should have … Read More →
Reverse every k nodes of a linked list
Given a linked list and a number k. Reverse every k nodes in the list. Example : Input 1->2->3->4->5->6 and k = 2 Output 2->1->4->3->6->5 Solution : We have a pointer q which points to the head of the list initially. Advance this k times in a while loop and keep reversing the list. Now … Read More →
Find loop in linked list and remove the loop
To remove the loop, we need to find the node at which the loop begins. Detection is easy by using fast and normal pointers (referred to as FP and NP from now on) to traverse such that the fast pointer traverses 2 nodes while normal pointer moves 1 node at a time. If they meet, … Read More →
Convert Sorted Linked list to balanced BST
In previous problem, we discussed how to create a balanced binary search tree for a sorted array. Now we’ll see how to create the same from a sorted linked list. Method 1: This solution is similar to our previous solution but unlike array accessing middle element of linked list is not O(1). Approach : i. … Read More →
What’s going on ?