HackerRank Day 24: More Linked Lists | Python
In this series, I will walk you through Hacker Rank’s 30 days of code challenge day by day.
In Day 24, we will work with Linked Lists in more depth by learning how to delete elements.
Please fill out this survey to help give me feedback on how to improve the channel.
http://bit.ly/2nVK9oM
Review Linked Lists in Day 15 Here.
http://bit.ly/2PVviHs
Try solving it yourself!
http://bit.ly/2LUAFn0
Join our LinkedIn Group to ask questions and learn from others.
/ 13664544
Support me on Patreon!
/ overtheshouldercoding
View my solution for Day 24 at
http://bit.ly/2CbGr4f
#OTSC #LinkedLists #HackerRank
Transcript
Today we're going to be diving into more depth with linked lists and learning how to remove elements from a linked list.
HackerRank will create a singly linked list for us that has non-decreasing elements. This means that each next element must be equal to or greater than the element before it. Their example list is 1, 2, 2, 3, 3, 4. Because the list is in non-decreasing order, we can easily identify duplicate elements by checking the next element's data to see if it equal. Since it is sorted in increasing order, we know that all the duplicate elements will be right next to each other.
So how do we delete an element from the linked list without breaking the list? Consider the example list. Each node has data and a pointer to the next node. If we delete either of the nodes with data 2, then we will be disconnecting the list into two separate lists. In order to keep the list connected, we will re-assign the node that the tail of the first list is pointing to. It will point to the head of the next list to keep them connected. So when we are deleting duplicates, we need to keep track of our current node, the next node, and the node 2 edges away. If we delete the next node, then we need to reassign the current node's next pointer to point to the node 2 edges away to keep the list linked.
OK Let's implement the remove duplicates method. Before we begin iterating through a linked list, we should first check to make sure we have proper inputs. If we do not have a head node, we will exit early and return None since we do not have a list to iterate over.
Next, we will track our current progress in the list with a current variable and while there are nodes after current, we will delete duplicates. We delete duplicates by checking if the next node's data is equal to our current node's data. If it is, we simply point our current node's next to the node 2 away which is our current node's next node's next node.
If the next node is not a duplicate, we can move our current pointer to the next node and check the nodes after it for duplicates. We can't immediately move the current pointer to the new next pointer we just reassigned because if we have multiple duplicates in a row, we will then delete every other duplicate instead of all duplicates after the original element. An example is if we have a list 1, 1, 1, 1. If we delete the second element, and move our current pointer to next immediately, we will now be on the 3rd element and delete the 4th because it is a duplicate of the 3rd but not delete the 3rd as a duplicate of the first.
![Star Citizen - Making Money with an Aurora [GIVEAWAY]](https://images.videosashka.com/watch/o7JyUhfZ3Wo)
