Reorder List | 3 Approaches | Leetcode 143 | codestorywithMIK
226Whatsapp Community Link : https://www.whatsapp.com/channel/0029Va6kVSjICVfiVdsHgi1A
This is the 22nd Video of our Playlist "Linked List : Popular Interview Problems".
In this video we will try to solve an easy but very good problem asked by Microsoft :
Reorder List | 3 Approaches | Leetcode 143 | codestorywithMIK
I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.
Also, please note that my Github solution link below contains both C++ as well as JAVA code.
Problem Name : Reorder List | 3 Approaches | Leetcode 143 | codestorywithMIK
Company Tags : Amazon, Microsoft, OYO
My solutions on Github(C++ & JAVA) : https://github.com/MAZHARMIK/Interview_DS_Algo/blob/master/Linked%20List/Reorder%20List.cpp
Leetcode Link : https://leetcode.com/problems/reorder-list/description/
My DP Concepts Playlist : https://youtu.be/7eLMOE1jnls
My Graph Concepts Playlist : https://youtu.be/5JGiZnr6B5w
My Recursion Concepts Playlist : https://www.youtube.com/watch?v=pfb1Zduesi8&list=PLpIkg8OmuX-IBcXsfITH5ql0Lqci1MYPM
My GitHub Repo for interview preparation : https://github.com/MAZHARMIK/Interview_DS_Algo
Instagram : https://www.instagram.com/codestorywithmik/
Facebook : https://www.facebook.com/people/codestorywithmik/100090524295846/
Twitter : https://twitter.com/CSwithMIK
Subscribe to my channel : https://www.youtube.com/@codestorywithMIK
Approach Summary :
**Approach-1 (Using stack):**
This approach utilizes a stack to reorder the given linked list. It first traverses the linked list, pushing each node onto the stack. Then, it calculates the midpoint of the linked list and rearranges the nodes by popping nodes from the stack and inserting them after the respective nodes from the original list. The process continues until reaching the end of the original list.
- Time Complexity (T.C): O(n), where n is the number of nodes in the linked list.
- Space Complexity (S.C): O(n) due to the stack used to store nodes.
**Approach-2 (Without stack):**
This approach doesn't use an explicit stack data structure. It first finds the midpoint of the linked list using two pointers (slow and fast). Then, it reverses the second half of the list. After that, it iterates through the original list, merging nodes from the front and back halves alternately until reaching the end.
- Time Complexity (T.C): O(n), where n is the number of nodes in the linked list.
- Space Complexity (S.C): O(1) auxiliary space, O(n) recursion stack space due to the reverse function.
**Approach-3 (Only Recursion):**
This approach solely relies on recursion to reorder the linked list. It recursively traverses to the end of the list, then rearranges the nodes in place while backtracking. It swaps the current node with the node pointed to by a class variable 'curr'. The process continues until the end of the list is reached.
- Time Complexity (T.C): O(n), where n is the number of nodes in the linked list.
- Space Complexity (S.C): O(1) auxiliary space and O(n) recursion stack space.
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
✨ Timelines✨
00:00 - Introduction
01:49 - Approach 1
09:52 - Coding Approach 1
12:31 - Approach 2
19:20 - Coding Approach 2
21:34 - Approach 3
37:22 - Coding Approach 3
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #newyear2024