Merge in Between Linked Lists - Leetcode 1669 - Python

NeetCodeIO · Intermediate ·⚡ Algorithms & Data Structures ·2y ago

Key Takeaways

The video demonstrates a solution to the Leetcode problem 1669, Merge in Between Linked Lists, using Python. The problem involves merging two linked lists by removing a section of nodes from the first list and inserting the second list in its place.

Full Transcript

hey everyone welcome back and let's write some more neat code today so today let's solve the problem merge in between linked lists so let's just focus on the example so straight to it we're given two link lists as you can see here and we're also given two integers here A and B so in this case if a is equal uh to 3 and b is equal to 4 what that means is we want to go to the third node and this is actually they don't mention it anywhere in the problem unless I missed it this is assuming this is zerob based so 0 1 2 3 4 and five so you can see from 3 to 4 we want to remove those nodes from 3 to four okay so that's not hard and in between like where that was we want to now insert the new linked list so as you can see this last node the node before the node that we removed is going to then point at the beginning of list two and as you can see the last node in list two is going to point at the node after the section that we removed and not only that we are actually guaranteed they kind of mention it down in the footnotes but we're pretty much guaranteed that a to be like this section that we remove is not going to include the head of the link list so that makes it really really convenient for us to be honest and so the way I'm going to go ahead and implement the solution to this problem is pretty much what I just talked about right now we're going to have a pointer that is going to pretty much iterate up until this node and then we're just going to have it point at list two then we're going to continue to iterate until we have a pointer to this node and lastly we're going to Traverse the entire second list going through that entire list so that then we can make the last uh node point at this node so pretty much we're going to go through both of the lists you can assume that the time complexity is n plus M where these are the sizes of the lists that they mention and no additional space complexity so it's going to be constant space The Reason by the way that this was such an easy explanation for me to give is that they actually gave us a very very good picture in this problem so much so that I would consider this actually more of an easy problem and the big takeaway I think from this problem is that pictures are so damn helpful for understanding these problems right that's kind of why I do this whiteboarding stuff they gave us the picture this time but usually you have to create it yourself so for harder problems this kind of problem solving skill of being able to draw out a picture is extremely helpful and I didn't really have a lot of notes uh this time for the problem to show you guys so let's just jump into the code so first I'm just going to have a pointer it's going to be at the beginning of list one we want this to point at the node before the node that we want to remove so I'm going to have a pointer and I'm actually going to set it to one because I want to say this while I is less than a we want to do this we want to shift the pointer and we want to increment I and the reason I set it to one is just because that's how the math works out like if I show you a linked list that let's say looks like this if a is uh three for example if a is three that means we want to remove starting from this node right because we're zero indexed and now that I think of it actually maybe a better way is to actually change this to a zero and then change this to a minus one so then pretty much what we're saying is I is going to represent the index which I think that's probably the more intuitive thing to do and then we're saying okay keep incrementing until I has reached the node that is right before a so if a is here we are going to stop once we reach this node which is exactly what we want to do so I think this is probably the better way to do it so now by the time this Loop is is done current should be pointing here and so even though now we want to set the next node of this to list two we can't do that just yet because we do want to iterate over the rest of this so we will write that code we'll say here that head is equal to a snapshot of what current is right now so head will basically point to this node and then eventually we're going to say head. next is equal to list two but we're going to save that for later so in between we're going to add some more code here because we want to Traverse the rest of this or at least up until uh B so we now want to get a pointer to this node or rather the node after that cuz we want to remove this section here so let me just make that very clear this is the section we're trying to remove and so we want a pointer here because we want the last node in list two to point here so let's say uh while I is less than or equal to B actually because if we say less than b we will stop here but we want to stop after that so we will continue one more time after that and then stop here so here let's just say current is equal to current. next and I + 1 and so now not only can we point this at the beginning of list two but now we can also iterate over list two just like this this is the easy part so while list two is non-null we can increment this or rather shift it to the next node like this but this is actually not good what this is going to do is it's going to keep shifting this pointer until we reach null list two will point at null that's not what we want we want the last node from list two so let's actually say while list 2. next is non-null and so this will stop at the last node and then with the last node we can say list 2. next is equal to tail and then we can return the head of list one which we we did not change and I don't know why actually I pointed this at tail we didn't Define tail so I guess I will change this to curve because remember after this Loop current is pointing at the node right after the one that we deleted so now let's go ahead and run the code and as you can see it works it's pretty efficient if you're preparing for coding interviews check out NE code. thanks for watching and I'll see you soon

Original Description

🚀 https://neetcode.io/ - A better way to prepare for Coding Interviews 🧑‍💼 LinkedIn: https://www.linkedin.com/in/navdeep-singh-3aaa14161/ 🐦 Twitter: https://twitter.com/neetcode1 ⭐ BLIND-75 PLAYLIST: https://www.youtube.com/watch?v=KLlXCFG5TnA&list=PLot-Xpze53ldVwtstag2TL4HQhAnC8ATf Problem Link: https://leetcode.com/problems/merge-in-between-linked-lists/ 0:00 - Read the problem 0:30 - Drawing Explanation 2:40 - Coding Explanation leetcode 1669 #neetcode #leetcode #python
Watch on YouTube ↗ (saves to browser)
Sign in to unlock AI tutor explanation · ⚡30

Playlist

Uploads from NeetCodeIO · NeetCodeIO · 0 of 60

← Previous Next →
1 Leetcode 149 - Maximum Points on a Line - Python
Leetcode 149 - Maximum Points on a Line - Python
NeetCodeIO
 2 Design Linked List - Leetcode 707 - Python
Design Linked List - Leetcode 707 - Python
NeetCodeIO
 3 Minimum Time to Collect All Apples in a Tree - Leetcode 1443 - Python
Minimum Time to Collect All Apples in a Tree - Leetcode 1443 - Python
NeetCodeIO
 4 Design Browser History - Leetcode 1472 - Python
Design Browser History - Leetcode 1472 - Python
NeetCodeIO
 5 Number of Good Paths - Leetcode 2421 - Python
Number of Good Paths - Leetcode 2421 - Python
NeetCodeIO
 6 Flip String to Monotone Increasing - Leetcode 926 - Python
Flip String to Monotone Increasing - Leetcode 926 - Python
NeetCodeIO
 7 Maximum Sum Circular Subarray - Leetcode 918 - Python
Maximum Sum Circular Subarray - Leetcode 918 - Python
NeetCodeIO
 8 Find Closest Node to Given Two Nodes - Leetcode 2359 - Python
Find Closest Node to Given Two Nodes - Leetcode 2359 - Python
NeetCodeIO
 9 Concatenated Words - Leetcode 472 - Python
Concatenated Words - Leetcode 472 - Python
NeetCodeIO
 10 Data Stream as Disjoint Intervals - Leetcode 352 - Python
Data Stream as Disjoint Intervals - Leetcode 352 - Python
NeetCodeIO
 11 LFU Cache - Leetcode 460 - Python
LFU Cache - Leetcode 460 - Python
NeetCodeIO
 12 N-th Tribonacci Number - Leetcode 1137
N-th Tribonacci Number - Leetcode 1137
NeetCodeIO
 13 Best Team with no Conflicts - Leetcode 1626 - Python
Best Team with no Conflicts - Leetcode 1626 - Python
NeetCodeIO
 14 Greatest Common Divisor of Strings - Leetcode 1071 - Python
Greatest Common Divisor of Strings - Leetcode 1071 - Python
NeetCodeIO
 15 Shortest Path in a Binary Matrix - Leetcode 1091 - Python
Shortest Path in a Binary Matrix - Leetcode 1091 - Python
NeetCodeIO
 16 Insert into a Binary Search Tree - Leetcode 701 - Python
Insert into a Binary Search Tree - Leetcode 701 - Python
NeetCodeIO
 17 Delete Node in a BST - Leetcode 450 - Python
Delete Node in a BST - Leetcode 450 - Python
NeetCodeIO
 18 Shuffle the Array (Constant Space) - Leetcode 1470 - Python
Shuffle the Array (Constant Space) - Leetcode 1470 - Python
NeetCodeIO
 19 Fruits into Basket - Leetcode 904 - Python
Fruits into Basket - Leetcode 904 - Python
NeetCodeIO
 20 Number of Subarrays of size K and Average Greater than or Equal to Threshold - Leetcode 1343 Python
Number of Subarrays of size K and Average Greater than or Equal to Threshold - Leetcode 1343 Python
NeetCodeIO
 21 Naming a Company - Leetcode 2306 - Python
Naming a Company - Leetcode 2306 - Python
NeetCodeIO
 22 As Far from Land as Possible - Leetcode 1162 - Python
As Far from Land as Possible - Leetcode 1162 - Python
NeetCodeIO
 23 Shortest Path with Alternating Colors - Leetcode 1129 - Python
Shortest Path with Alternating Colors - Leetcode 1129 - Python
NeetCodeIO
 24 Minimum Fuel Cost to Report to the Capital - Leetcode 2477 - Python
Minimum Fuel Cost to Report to the Capital - Leetcode 2477 - Python
NeetCodeIO
 25 Count Odd Numbers in an Interval Range - Leetcode 1523 - Python
Count Odd Numbers in an Interval Range - Leetcode 1523 - Python
NeetCodeIO
 26 Contains Duplicate II - Leetcode 219 - Python
Contains Duplicate II - Leetcode 219 - Python
NeetCodeIO
 27 Path with Maximum Probability - Leetcode 1514 - Python
Path with Maximum Probability - Leetcode 1514 - Python
NeetCodeIO
 28 Add to Array-Form of Integer - Leetcode 989 - Python
Add to Array-Form of Integer - Leetcode 989 - Python
NeetCodeIO
 29 Unique Paths II - Leetcode 63 - Python
Unique Paths II - Leetcode 63 - Python
NeetCodeIO
 30 Minimum Distance between BST Nodes - Leetcode 783 - Python
Minimum Distance between BST Nodes - Leetcode 783 - Python
NeetCodeIO
 31 Design Hashmap - Leetcode 706 - Python
Design Hashmap - Leetcode 706 - Python
NeetCodeIO
 32 Range Sum Query Immutable - Leetcode 303 - Python
Range Sum Query Immutable - Leetcode 303 - Python
NeetCodeIO
 33 Binary Tree Zigzag Level Order Traversal - Leetcode 103 - Python
Binary Tree Zigzag Level Order Traversal - Leetcode 103 - Python
NeetCodeIO
 34 Middle of the Linked List - Leetcode 876 - Python
Middle of the Linked List - Leetcode 876 - Python
NeetCodeIO
 35 Course Schedule IV - Leetcode 1462 - Python
Course Schedule IV - Leetcode 1462 - Python
NeetCodeIO
 36 Single Element in a Sorted Array - Leetcode 540 - Python
Single Element in a Sorted Array - Leetcode 540 - Python
NeetCodeIO
 37 Capacity to Ship Packages - Leetcode 1011 - Python
Capacity to Ship Packages - Leetcode 1011 - Python
NeetCodeIO
 38 IPO - Leetcode 502 - Python
IPO - Leetcode 502 - Python
NeetCodeIO
 39 Minimize Deviation in Array - Leetcode 1675 - Python
Minimize Deviation in Array - Leetcode 1675 - Python
NeetCodeIO
 40 Longest Turbulent Array - Leetcode 978 - Python
Longest Turbulent Array - Leetcode 978 - Python
NeetCodeIO
 41 Last Stone Weight II - Leetcode 1049 - Python
Last Stone Weight II - Leetcode 1049 - Python
NeetCodeIO
 42 Construct Quad Tree - Leetcode 427 - Python
Construct Quad Tree - Leetcode 427 - Python
NeetCodeIO
 43 Find Duplicate Subtrees - Leetcode 652 - Python
Find Duplicate Subtrees - Leetcode 652 - Python
NeetCodeIO
 44 Sort an Array - Leetcode 912 - Python
Sort an Array - Leetcode 912 - Python
NeetCodeIO
 45 Ones and Zeroes - Leetcode 474 - Python
Ones and Zeroes - Leetcode 474 - Python
NeetCodeIO
 46 Remove Duplicates from Sorted Array II - Leetcode 80 - Python
Remove Duplicates from Sorted Array II - Leetcode 80 - Python
NeetCodeIO
 47 Maximum Twin Sum of a Linked List - Leetcode 2130 - Python
Maximum Twin Sum of a Linked List - Leetcode 2130 - Python
NeetCodeIO
 48 Concatenation of Array - Leetcode 1929 - Python
Concatenation of Array - Leetcode 1929 - Python
NeetCodeIO
 49 Symmetric Tree - Leetcode 101 - Python
Symmetric Tree - Leetcode 101 - Python
NeetCodeIO
 50 Check Completeness of a Binary Tree - Leetcode 958 - Python
Check Completeness of a Binary Tree - Leetcode 958 - Python
NeetCodeIO
 51 Construct Binary Tree from Inorder and Postorder Traversal - Leetcode 106 - Python
Construct Binary Tree from Inorder and Postorder Traversal - Leetcode 106 - Python
NeetCodeIO
 52 Find Peak Element - Leetcode 162 - Python
Find Peak Element - Leetcode 162 - Python
NeetCodeIO
 53 Accounts Merge - Leetcode 721 - Python
Accounts Merge - Leetcode 721 - Python
NeetCodeIO
 54 Binary Tree Preorder Traversal (Iterative) - Leetcode 144 - Python
Binary Tree Preorder Traversal (Iterative) - Leetcode 144 - Python
NeetCodeIO
 55 Binary Tree Postorder Traversal (Iterative) - Leetcode 145 - Python
Binary Tree Postorder Traversal (Iterative) - Leetcode 145 - Python
NeetCodeIO
 56 Number of Zero-Filled Subarrays - Leetcode 2348 - Python
Number of Zero-Filled Subarrays - Leetcode 2348 - Python
NeetCodeIO
 57 Minimum Score of a Path Between Two Cities - Leetcode 2492 - Python
Minimum Score of a Path Between Two Cities - Leetcode 2492 - Python
NeetCodeIO
 58 Sqrt(x) - Leetcode 69 - Python
Sqrt(x) - Leetcode 69 - Python
NeetCodeIO
 59 Successful Pairs of Spells and Potions - Leetcode 2300 - Python
Successful Pairs of Spells and Potions - Leetcode 2300 - Python
NeetCodeIO
 60 Optimal Partition of String - Leetcode 2405 - Python
Optimal Partition of String - Leetcode 2405 - Python
NeetCodeIO

The video teaches how to solve the Leetcode problem 1669, Merge in Between Linked Lists, using Python. The solution involves iterating through the linked lists, removing a section of nodes, and inserting the second list in its place.

Key Takeaways
  1. Initialize pointers to the beginning of the first linked list
  2. Iterate through the first linked list to find the node before the section to be removed
  3. Remove the section of nodes from the first linked list
  4. Insert the second linked list in place of the removed section
  5. Iterate through the second linked list to find the last node
  6. Set the last node of the second linked list to point to the node after the removed section
💡 Pictures can be very helpful in understanding complex problems, and being able to draw out a diagram can be an extremely useful problem-solving skill.

Related AI Lessons

⚡
Bloom Filters, Explained Properly
Learn how Bloom filters work and their benefits, including tiny memory and blazing speed, in exchange for potential false positives.
Dev.to · Daksh Gargas
 ⚡
Prefix Sums: The Preprocessing Trick That Makes Range Queries Instant
Learn how prefix sums enable instant range queries in arrays, boosting performance in various applications
Medium · Programming
 ⚡
I Thought I Was Ready for the Interview — Then One Simple Math Question Destroyed Me
A simple math question can destroy a developer's interview, highlighting the importance of being prepared for unexpected questions
Medium · Programming
 ⚡
Week 2(Day 10): LeetCode Two Pointers(slow & fast): Remove Duplicates from Sorted Array (Brute…
Learn to remove duplicates from a sorted array using the two pointers technique, improving from brute force to optimized solutions
Medium · Python

Chapters (3)

Read the problem
0:30 Drawing Explanation
2:40 Coding Explanation
Up next
Stump Grinder Carbide Wheel Grinds Hardwood To Chips
Innoforge Studio
Watch →