Posted on by Kalkicode

# Remove last node of the linked list

The problem at hand involves manipulating a singly linked list, specifically deleting the last node from the list. A singly linked list is a linear data structure consisting of nodes, where each node contains a value and a reference to the next node in the sequence. Deleting the last node involves updating the pointers of the second-to-last node to point to NULL, effectively removing the last node from the list.

## Problem Statement and Description

Given a singly linked list, the task is to delete the last node from it while maintaining the integrity of the list. This entails updating the previous node's pointer to NULL and freeing the memory occupied by the deleted node.

## Example

Consider the linked list: 1 → 2 → 3 → 4 → 5 → 6.

• Before Deleting Last Node
• Linked List: 1 → 2 → 3 → 4 → 5 → 6
• Explanation: This is how the linked list looks before deleting the last node.
• After Deleting Last Node
• Linked List: 1 → 2 → 3 → 4 → 5
• Explanation: The last node (6) has been removed from the linked list, and the previous node's pointer (node 5) is updated to point to NULL.

## Idea to Solve

1. Traverse the linked list to find the second-to-last node. This can be achieved by iterating until the next node's next pointer is not NULL.
2. Once the second-to-last node is found, update its next pointer to NULL, effectively removing the last node.
3. Update the tail pointer of the linked list to point to the new last node.
4. Free the memory occupied by the deleted last node.

## Pseudocode

``````deleteLastNode(sll):
return

find = NULL
while temp.next is not NULL:
find = temp
temp = temp.next

if find is NULL:
sll.tail = NULL
else:
sll.tail = find
find.next = NULL

free(temp)``````

## Algorithm Explanation

1. Check if the linked list is empty. If so, there's nothing to delete, so return.
2. Initialize a temporary pointer `temp` to point to the head of the linked list and another pointer `find` to keep track of the second-to-last node.
3. Traverse the linked list using the `temp` pointer to find the second-to-last node. The loop condition checks for `temp`'s next pointer not being NULL.
4. After exiting the loop, `temp` will be pointing to the last node, and `find` will be pointing to the second-to-last node.
5. Check if `find` is still NULL. If so, the linked list had only one node. Update both `head` and `tail` pointers to NULL.
6. If `find` is not NULL, update the `tail` pointer to point to `find`, and set `find`'s next pointer to NULL, effectively detaching the last node.
7. Free the memory occupied by the last node pointed to by `temp`.

## Time Complexity

• The algorithm involves traversing the linked list to find the second-to-last node. This takes O(n) time, where n is the number of nodes in the linked list.
• The rest of the operations involve adjusting pointers and freeing memory, which are constant-time operations.
• Hence, the overall time complexity of the algorithm is O(n).

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post