Dear reader, I welcome you to a problem named "Add Last in Linked List". Trust me, knowing this basic concept will help you solve hard category problems based on linked lists.
Important Links : Problem Link, Question Video, Solution Video
Add Last in Linked List
Computer Engineers don't fall in love. They just "link" with someone
~Sheer Angel
Dear reader, I welcome you to a problem named "Add Last in Linked List". Trust me, knowing this basic concept will help you solve hard category problems based on linked lists.
Important Links : Problem Link, Question Video, Solution Video
Note: You just need to complete the code of the addLast function, all other input/output methods and data members are managed for you.
I recommend you to watch the question video, where the problem statement is explained in detail.
Firstly, we should create a node with data = val and it's next pointer should point to null for the time being.
There are two cases which need to be handled:
If the linked list is empty, then head and tail are currently pointing to null. Hence, the node we are about to add should become both the head node as well as the tail node of the linked list.
Otherwise, if the linked list is not empty, then we will have to append the node at the end of the linked list, i.e. the next pointer of the last node should point to the new node inserted. Also, this new node should now be the tail node of the linked list.
In either of the two cases, we are increasing the size of the linked list by 1.
Please refer to the solution video if you find difficulty in understanding the algorithm completely.
How about first trying by yourself without reading the code we provide?
java; true";
This code is written and explained by our team in this video. Please refer to it if you are stuck somewhere.
Example: Let us dry run the algorithm using a few addLast operations.
First, we are creating a new node, which is a constant O(1) operation. Then, if the size = 0, then make head and tail point to temp, which is again O(1). Else, we are updating tails' next as temp and updating tail as temp, which is O(1) again. Also, updating size by 1 is constant O(1) operation.
Hence, the total time complexity is O(1) only.
We are creating only one node which has data and a pointer to the next node, hence auxiliary space required is constant O(1).
Note that the space complexity is equal to the size of the linked list, i.e. O(n), but we are required to find the extra space taken by the addLast function only.
Don't worry, we will see how to traverse a linked list and display it in the next problem. I hope you enjoyed solving the problem with me. The next problem waiting for you is to display an entire linked list.
Please try to be consistent in your daily coding practice routine. Giving a considerable amount of effort consistently for a long duration (5-6 months) will be more productive than being rigorous and trying to grab all the knowledge in just 2-3 weeks.