Understanding deletion of last node

We must access the second last node to delete the last node from a linked list. Then, we can update the next pointer of this second last node to null and delete the last node. This process involves traversing the linked list and keeping track of the previous node (similar to inserting a node at the end). Let's go through the specific cases we need to consider.

1. The list is empty

When the list is empty, meaning it contains no elements, any attempt to delete a node is unnecessary because there are no nodes in the list. Since there is nothing to remove, the list remains unchanged. We can return the existing head, as the list is empty, and no node needs to be deleted.

Algorithm

• Step 1: Return the original head node.

2. The list has only one node

Deleting the last node is the same as deleting the first node when only one node is in the list. We follow the same steps in both cases, such as deleting the first/last node. This involves deleting the head node and returning null.

Algorithm

• Step 1: Delete the head node to free up memory.
• Step 2: Return `null` as the list is now empty.

3. The list has more than one node

In this scenario, we need to update the next pointer of the second last node in the list to hold null and then delete the last node. We need access to the list's last and second last nodes to accomplish this. We will traverse the list from the beginning while keeping track of the current and previous nodes. This way, when we reach the last node, we will have access to the second last node. Thereafter, we can update the next pointer of the second last node to null, or more intuitively, to the next of the last node, which should already be null, and then delete the last node.

Algorithm

• Step 1: Traverse the list while keeping track of the `current` and `previous` nodes until reaching the last node.
• Step 2: Set the `next` pointer of the `previous` node to `null`.
• Step 3: Delete the last node to free up memory.
• Step 4: Return the original head node.

Implementation

When implementing the logic for deleting the last node operation, we consider all the possible cases and subcases and write the code for each in conditional blocks.

Complexity Analysis

The time complexity of the above function depends on the number of nodes in the linked list. Since we must traverse the entire list to reach the end, its time complexity is O(N), where N is the number of nodes in the list.

The function's space complexity is O(1) because it only creates a single new node and does not use any additional data structures.

Best Case

• Space Complexity - O(1)
• Time Complexity - O(N)

Worst Case

• Space Complexity - O(1)
• Time Complexity - O(N)