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):
    if sll.head is NULL:
        return

    temp = sll.head
    find = NULL
    while temp.next is not NULL:
        find = temp
        temp = temp.next
    
    if find is NULL:
        sll.head = 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.

Code Solution

1) Delete last node of linked list in c 2) Delete last node of linked list in c++ 3) Delete last node of linked list in java 4) Delete last node of linked list in c# 5) Delete last node of linked list in php 6) Delete last node of linked list in python 3 7) Delete last node of linked list in javascript 8) Delete last node of linked list in go 9) Delete last node of linked list in kotlin 10) Delete last node of linked list in swift 11) Delete last node of linked list in scala 12) Delete last node of linked list in ruby 13) Remove last node of the linked list in vb.net 14) Remove last node of the linked list in typescript

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).