Split Linked List in Parts - Leetcode 725 - Python

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

Key Takeaways

The video demonstrates how to solve LeetCode problem 725, splitting a linked list into K parts, using a greedy approach and a two-pointer technique in Python.

Full Transcript

hey everyone welcome back and let's write some more neat code today so today let's solve the problem split linked list in Parts it's similar to a lot of the other link list problems but this is like a slight variation there's a lot of problems where you actually have to split link lists some of the ideas are going to be the same we're given the head of a singly link list and an integer K and the catch here is that we want to take this linked list and split it into K Parts but actually K might be larger than n where n is the number of nodes given to us so that's kind of weird but it's still doable it's not like conceptually hard the code is a little bit tricky to get but once you know it it's actually pretty straightforward the first thing to do is just go through some examples the first example they gave us here is actually not too bad because it illustrates exactly that idea K is five so what do we do well we split the linked list and we want to do it in a sort of greedy way where we start at at the beginning and we start taking nodes from the beginning we want to split the link list into roughly equal parts as equal as we can get them and if there is a difference the difference has to be no more than one and if any of the link lists are going to be empty which is going to be the case here they have to go at the end so here we start with the first node we take that as a link list and when we do that we're going to add it to the output result not just the value of it but we're actually going to take take the linked list and add it to the output and if we're going to do that we don't want this to actually be connected to the next node anymore so that's just something we're going to have to keep track of we're going to get rid of this pointer and this is going to now be pointing at null we'll still need to be able to jump to this next one when we try to build the second linked list so that's just something we have to keep in mind that's just part of the pointer manipulation that always is the case when it comes to link list problems and then the second note here we're going to do the exact same thing this is going to be the second link list this is going to point at null then once again this is going to be the third link list and that's the last one now we can try to keep building more but the fourth one is going to be empty and the fifth one is also going to be empty we have five because remember that's what was required of us in this example so this example is pretty straightforward but what if we actually had six nodes and K is still equal to 5 then what would we do this is not the cleanest way to draw it but just let's just pretend that this is a a length list of length six so how would we split this up let's just think about what the result would look like remember we want to be greedy so the longest linked lists are going to go at the beginning so if we were to split this up into five linked lists we can't just pick one node for each because then we're going to have one guy left over that's not allowed so one of these link lists has to have at least two nodes and that's going to have to be the first one the way this problem is defined and then the next ones are each going to have a single node so if we had maybe a seventh node it would be similar in that the first two linked lists would each have two nodes then this one would have one this one would have one and this one would have one so this is kind of a math problem at this point what we're noticing is that some of the linked lists are going to have an extra node and in the first example here when we just had three nodes the first three had an extra node meaning they had just a single node and the last two had zero nodes that rule of having an extra node still applies some of the link lists are going to have an extra node some of them are not going to have an extra node how do we determine how many extra nodes we even have well first we want to know like the base length of each linked list how would we determine that well we would take the length of the link list the number of nodes let's call that n and divide it by by K and we would round this down now in this case we have 5 / 3 that's going to give us zero the base length is zero that makes sense cuz the last two had a length of zero if we had a length of six as I showed earlier we'd have 6 divided by five round that down we'd get one so this rule does work so far now how do we determine how many extra nodes we have just just take a look at this computation I bet you can figure it out how do we know how many extra nodes we we have well instead of dividing how about we get the remainder six modded with five is going to leave us with a remainder of one so that means one linked list is going to have an extra node if we did seven modded by five that means two link lists are going to have an extra node so once you get to this part like you know what the base length you can compute the base length of each linked list and you can figure out how many extra nodes we have you've pretty much solved the problem at least conceptually and after that it just becomes a matter of coding it up which is kind of annoying CU we have to do like a lot of edge cases and stuff but it's very very doable now time complexity wise we're basically going to count the length of the linked list and then we're going to iterate over one more time so you would think the time complexity is just going to be Big O of n where n is the length of the length list but remember K might be longer than the length and we do have to build the output so I guess we can say the time complexity is going to be the max of n and K so now let's go ahead and code this up okay so the first thing like I said we want to get the length of the link list and I'm also going to use a second pointer to do that because we don't want to get rid of our head pointer if we update that then we won't be able to reach the head again so I'm going to start at the head and we're just going to keep shifting this pointer one by one and incrementing the length as we do that by the end of this we will have the entire length of the linked list and then we want to get the base length I guess I'll call that the subl length because it's a little bit shorter or actually why not let's just call it base length and I'm also going to get the remainder aka the extra nodes and we can get the subl length by taking the length and dividing it by K double slash is integer division in Python that's important here in most languages I don't think you need to do that also length modded by K is going to give us the remainder now we want to start at the head of the link list again so I'm going to set CER to head I'm also going to initialize an empty list as the result this is what we're going to be returning now we're going to iterate over the link list we're not going to do while Cur because that would yes split this link list up into like the parts that we're looking for but we know we might have some empty Parts even if current is null we still want to keep going and we want to iterate exactly K times or at least we want to build exactly K lists even if some of them are empty now wherever our current pointer is right now that's going to be the head of the current part of the link list we might as well add it to the result at this point now we do have to set like the end of that part we have to point the next pointer of the end of this part to null so we're going to now at this point keep looping again and for this I guess I'll have a different pointer for J in range how many times do we want to iterate well probably the subl length of the length list or I guess this time I called it Bas length and we want to add one if the remainder is non zero so I'm going to do that with a Turner operator one if remainder is non zero else add zero so this is just like a clever way of kind of doing it you can write it out more explicitly if you want to like here with a separate variable or something but this works now one thing to know here is like suppose we had a linked list that looks like this let's say our current pointer is here and the length of the entire list is six and we want to split it into two parts so this would be one part and this would be another part so starting from one we want to get to the end of the current part so that we can take this and set its next pointer equal to null so how many times do we have to iterate one if we're starting here 1 2 so even though the length of the part the base length is three we actually want to iterate the base length minus one that's why I'm going to put a minus one here and theoretically like the remainder won't necessarily change that like let's just suppose that this was actually a list of length seven and it looked like this well for the first part we would want it to be of length four the remainder will still work for that and this one we would want it to be of length three so the computation works out in both cases so now that we have that what do we actually want to do in this Loop just set the current pointer equal to curve. next remember that some of the parts might be null so what happens if our current pointer is at null well at that point we might as well break so if not Cur just break out of the loop so that works and we also at this point before we take the pointers and start updating them we should also decrement our current remainder but what happens when the remainder reaches zero and then we decrement it again then it's going to be -1 and that's going to screw this tary operator up so we're actually going to decrement this only decrement it by one if the remainder is nonzero otherwise decrement it by zero AKA don't change it at all again this is kind of a clever way of doing it you can definitely write it out more explicitly if you want I encourage you to do that if that makes more sense like maybe make an if statement if remainder is greater than zero then decrement it if not then don't decr it we're almost done one last thing to do we reach the end of the current part but now we need to set the end of the current part equal to null so we can set current. nextt equal to null but again remember current might already be null so let's make sure that it's not before we do that now that we've done that we also want to shift the current pointer to the head of the next part so we want to shift it by one we can't do that after we've set the next pointer equal to null like that won't work obviously so in most languages you can create a temporary variable to do that in Python though you can actually do that in a single line like this so I can get rid of this bottom part and I believe this is the entire code so let's run it to make sure that it works and it's always a small thing for me so I forgot the else over here even though I remembered it up here now let's try that again and as you can see on the left it works it's pretty efficient if you found this helpful please like And subscribe if you're preparing for coding interviews check out NE code. and I'll see you soon

Original Description

Solving leetcode 725, split linked list in parts. Today's daily leetcode problem on September 5. 🚀 https://neetcode.io/ - A better way to prepare for Coding Interviews 🥷 Discord: https://discord.gg/ddjKRXPqtk 🐦 Twitter: https://twitter.com/neetcode1 🐮 Support the channel: https://www.patreon.com/NEETcode ⭐ BLIND-75 PLAYLIST: https://www.youtube.com/watch?v=KLlXCFG5TnA&list=PLot-Xpze53ldVwtstag2TL4HQhAnC8ATf 💡 DYNAMIC PROGRAMMING PLAYLIST: https://www.youtube.com/watch?v=73r3KWiEvyk&list=PLot-Xpze53lcvx_tjrr_m2lgD2NsRHlNO&index=1 Problem Link: https://leetcode.com/problems/split-linked-list-in-parts/ 0:00 - Read the problem 0:30 - Drawing Explanation 5:33 - Coding Explanation leetcode 725 #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

This video teaches how to solve LeetCode problem 725 by splitting a linked list into K parts using a greedy approach and a two-pointer technique in Python. The solution is efficient and works correctly, making it a great resource for coding interviews.

Key Takeaways
  1. Go through examples to understand the problem
  2. Split the linked list into K parts using a greedy approach
  3. Determine the base length of the list
  4. Calculate the number of extra nodes
  5. Get the length of the linked list using a second pointer
  6. Get the base length by dividing the length by K and rounding down
  7. Get the remainder to determine the number of extra nodes
  8. Start at the head of the linked list and iterate K times to split it into parts
  9. Add each part to the result list and set the next pointer to null
💡 The key to solving this problem is to use a greedy approach to split the linked list into roughly equal parts, with a maximum difference of one between parts.

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
5:33 Coding Explanation
Up next
Stump Grinder Carbide Wheel Grinds Hardwood To Chips
Innoforge Studio
Watch →