Problems based on the Linked list data structure
Completion Status | Linked List Problem | Explanation | Solution |
---|---|---|---|
✅ | Reverse Linked List | Iterative Approach | Java Soultion |
✅ | Middle of the Linked List | Brute - Optimal Approach | Java Soultion |
✅ | Merge Two Sorted Lists | Brute force Approach | Java Soultion |
✅ | Remove Nth Node From End of List | Iterative Approach | Java Soultion |
✅ | Delete Node in a Linked List | Iterative Approach | Java Soultion |
✅ | Add Two Numbers | Iterative Approach | Java Soultion |
- Create a dummy node - newHead and point it to null.
- Run a loop until the head of LL reaches null.
- For each iteration, create a node next which stores the next reference of head.
- Break the next reference of the head by pointing it towards the newHead.
- Reassign newHead with head and then head with node next.
- Return the newHead
- Time Complexity: O(N) | Space Complexity: O(1)
- Count all nodes in the given Linked list in one iteration
- Now, calculate mid as the count by two and add one only if the size is even
- Traverse again to reach the mid and return the mid node
- Time Complexity: O(N) + O(N/2) | Space Complexity: O(1)
- Take two nodes slow and fast and point them to the head node.
- Move the slow node by a distance of one and the fast node by a distance of two.
- When the fast node completes the traversal, the slow node has reached the middle.
- Return the slow node.
- Time Complexity: O(N/2) | Space Complexity: O(1)
- Take the head nodes of the given two linked lists as h1 and h2
- Create a dummy node d initialized to null
- Compare the node values of h1 and h2 and take the smaller one
- Create a new linked list and insert the smaller value into the LL.
- Now, point next of the dummy node to the LL, and create another duplicate dummy node dd to create new nodes
- If both of the heads h1 and h2 reach null, point the dd node to null as well.
- Repeat the comparisons and return dummy node d as the new head of LL.
- Time Complexity: O(n1 + n2) | Space Complexity: O(n1 + n2)
- Take two dummy nodes l1 and l2 pointing to larger and smaller LLs respectively
- Point l1 to whichever node value is smaller among given LLs and point l2 to larger node value
- Take another dummy node res which points to l1. This res is the resultant answer by the end of function execution
- Take a dummy node temp to store the smaller value among LL ( Basically to remember the last smallest node )
- Traverse through the LLs until:
- l1 is smaller than l2
- Reassign the value to temp
- When l1 becomes greater than l2:
- Break the next of temp
- Point the next of temp to l2
- Swap l1 and l2 ( Because l1 got bigger than l2)
- Change temp to null
- Repeat this iteration until l1 becomes null
- Time Complexity: O(n1 + n2) | Space Complexity: O(1)
- Check for every node in second LL to check each node in first LL for equality
- When you found equal nodes return it, else you will reach the end hence return null
- Time Complexity: O(m * n); where m and n are length of LL 1 & 2 respectively
- Traverse through first LL and hash the Node Address
- Again traverse for second LL and check for equality
- When you found equal node address from HashMap return it, else you will reach the end hence return null
- Time Complexity: O(m + n); where m and n are length of LL 1 & 2 respectively
- Space Complexity: O(m); where m and n are length of LL 1 & 2 respectively
- Take dummy nodes at head of both LL, and keep a count to store length of both the LL
- Take dummy nodes at head of both LL again, and cover the difference one LL using lengths
- Then, traverse simultaneously both the nodes to reach an intersection point
- When you found equal nodes return it, else you will reach the end hence return null
- Time Complexity = O(m) <= O(2m) <= { O(m) + O(m-n) + O(n) }; where m is length of longer LL and n is length of shorter LL
- Take two dummy nodes d1 and d2, assign them to head of the LL
- Move d1 and d2 simultaneously till one of them reaches null
- Now, reassign that dummy node that is at null to the head of the other LL
- Repeat the same process for both nodes until them meet at intersection
- When you found equal nodes return it, else you will reach the end hence return null
- The first iteration is to find the difference directly and reassigning them to equate the difference
- Hence in the second iteration they either meet at intersection if exists or null
- This approach is similar Optimal approach I, but instead of calculating difference, here we directly find it with our logic
- Time Complexity: O(2m); where m is the length of longer LL
- Take a dummy node d and traverse through the Linked List
- Create a HashMap to store Nodes and check whether the nodes exist already
- Hash the node itself if it's not present in the HashMap
- Return the point where the node exists or when we reach null
- Time Complexity: O(N) | Space Complexity: O(N)
- Take two pointers slow and fast
- Traverse slow pointer by one step and fast pointer by two steps
- If cycle exists, we can be pretty sure slow and fast pointer meet again
- If not then return null
- Time Complexity: O(N) | Space Complexity: O(1)
- As the fast pointer moves by two steps, ultimately it will meet at any one point
- Take four dummy nodes
- One to point to the new head of LL
- Other three to keep track of previous node, current node and the next node
- Apply reversing LL technique for k groups and keep on updating the dummy nodes
- Return the new head
- Time Complexity: O(N) | Space Complexity: O(1)
Dry Run
- Hash all the nodes in a HashMap
- When the same node occurs twice return it, else return null
- Time Complexity: O(N) | Space Complexity: O(N)
-
- Find the collision point
- Move slow pointer by 1 step and fast pointer by 2 steps
- They are bound to collide at one node if there exists a cycle
-
- Find the Starting point of LL Cycle
- Take entry pointer from head of LL
- Move both entry and slow pointers by 1 step
- When entry and slow pointers collide, that's the starting point of the LL
- Hence return that node
- If no cycle exists, fast will reach null, hence return it
- Time Complexity: O(N) | Space Complexity: O(1)
- The problem states that we are given a LL with two pointers - next and bottom
- We have to flatten given LL in such a way that the first node must contain all other nodes connected using bottom pointer in a sorted order
- So, if we can try to sort each LL from the back, we can reach to the solution
- We can sort two linked lists recursively using Merge Two Sorted LL logic
- Time Complexity: O(N) | Space Complexity: O(1)
Dry Run
- Rotate the LL by indivdually adding nodes from the end
- Time Complexity: O(k * N) | Space Complexity: O(1)
- Count the length of Linked list
- Correct the value of k
- Point last node to first node, once you are done with first step itself
- Traverse for
len-k
times, and save the next node in temp - Then break the next's link and reassign it to null
- Return the temp
- Time Complexity: O(N) | Space Complexity: O(1)
Dry Run
- Hash the current node with new duplicate node for the first traversal
- Assign next and random pointers, one by one, using Hashmap for the next traversal
- Return the new clone (deep copy) of LL
- Copy nodes and insert them right after the original nodes
- In the next iteration, Assign random pointers for the copy nodes using a dummy node
iter
and original nodes - Restore the original list, and extract the copy list
- Introduction
- Linked Lists VS Arrays
- Operations
- Implementation:
- Singly Linked List
- Doubly Linked List
- Circular Linked List
- Collections Framework
- List Interface
- LinkedList Class
- Time and Space Complexity
- Fast and slow pointer
- Cycle Detection
- Reversal of LinkedList
- Problems
- Reverse Linked List
- Reverse Linked List II
- Middle of the Linked List
- Merge Two Sorted Lists
- Delete Node in a Linked List
- Remove Nth Node From End of List
- Remove Linked List Elements
- Remove Duplicates from Sorted List
- Add Two Numbers
- Add Two Numbers II
- Intersection of Two Linked Lists
- Linked List Cycle
- Reverse Nodes in k-Group
- Palindrome Linked List
- Linked List Cycle II
- Flattening a Linked List
- Rotate List
- Implement Stack using Linked List
- Implement Queue using Linked List
- LRU Cache
- Copy List with Random Pointer
- Segregate Even Odd
- Union and Intersection
- Detect and Remove cycle
- Clone LinkedList
- Linked List are linear data structures where every element is a separate object with a data part and address part.
- Each object is called a Node.
- The nodes are not stored in contiguous locations. They are linked using addresses.
- In a linkedlist we can create as many nodes as we want according to our requirement. This can be done at the runtime.
- The memory allocation done by the JVM at runtime is known as DYNAMIC MEMORY ALLOCATION.
- Thus, linked list uses dynamic memory allocation to allocate memory to the nodes at the runtime.
Linked Lists | Arrays |
---|---|
Linked lists can grow dynamically | Array cannot grow Dynamically |
Sequential access of elements is possible | Random access of elements is possible |
- Middle of the Linked List
- Remove Nth Node From End of List
Amazon
,Microsoft
,Adobe
Linked List - Singly + Doubly + Circular (Theory + Code + Implementation | Linked List Interview Questions - Google, FAANGM |
---|---|