text:  remove the last node of the given list.
  Problem Statement Understanding
  Suppose, the given linked list is 1 -> 5 -> 9 -> 11 -> 20. Now, we are asked to delete the last node of the given list.
  Here, the last node is 20. So, after deleting the last node, the final linked list is 1 -> 5 -> 9 -> 11.
  Input:
  Output:
  Explanation: As the last node is 20, it is getting removed from the given list.
  As we know, insertion and deletion in a singly linked list are very efficient, but list traversal takes O(n) time. We are going to use the list traversal, but with a few tweaks. Let us have a glance at the approach.
  Approach
  The approach is going to be pretty simple. To remove the last node, what we can do is, reach the second last node, and make it point to NULL. By doing this, we are deleting the last node and making the second last node our new last node.
  Algorithm
  - Base Case 1 - If the head is NULL, return NULL
  - Base Case 2 - if head -> next is NULL, delete the head and return NULL.
  - This means that there was only a single node in the linked list.
  - Create a new node, say SecondLast and make it point to the head of the list.
  - Now, traverse through the list by incrementing SecondLast, till the second last node of the linked list is reached.
  - When we reach the second last node of the linked list, simply delete the next of the second last node i.e delete the last node.
  - delete(SecondLast -> next).
  - Make the second last node point to NULL. This will make our second last node new tail of the list.
  - Return head.
  Dry Run
  Code Implementation
  #include
  using namespace std; struct Node { int data; struct Node* next; }; Node* removeLastNode() { Node* head = NULL; push(&head, 20); push(&head, 11); push(&head, 9); push(&head, 5); push(&head, 1); head = removeLastNode(head); for (Node* temp = head; temp != NULL; temp = temp->next) cout << temp->data << " "; return 0; }
  public class PrepBytes { static class Node { int data; Node next; }; static Node removeLastNode(Node head) { if (head == null) return null; if (head.next == null) { return null; } Node second_last = head; while (second_last.next.next != null) second_last = second_last.next; second_last.next = null; return head; } static Node push(Node head_ref, int new_data) { Node new_node = new Node(); new_node.data = new_data; new_node.next = (head_ref); (head_ref) = new_node; return head_ref; } public static void main(String args[]) { Node head = null; head = push(head, 20); head = push(head, 11); head = push(head, 9); head = push(head, 5); head = push(head, 1); head = removeLastNode(head); for (Node temp = head; temp != null; temp = temp.next) System.out.print(temp.data + " "); } }
  #include
  #include struct Node { int data; struct Node* next; }; /* Function to remove the last node of the linked list */ struct Node* removeLastNode(struct Node* head) { if (head == NULL) return NULL; if (head->next == NULL) { free(head); return NULL; } // Find the second last node struct Node* second_last = head; while (second_last->next->next != NULL) second_last = second_last->next; // Delete last node free(second_last->next); // Change next of second last second_last->next = NULL; return head; } // Function to push node at head void push(struct Node** head_ref, int new_data) { struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; } // Driver code int main() { /* Start with the empty list */ struct Node* head = NULL; /* Use push() function to construct the below list 8 -> 23 -> 11 -> 29 -> 12 */ push(&head, 12); push(&head, 29); push(&head, 11); push(&head, 23); push(&head, 8); head = removeLastNode(head); for (struct Node* temp = head; temp != NULL; temp = temp->next) printf("%d ",temp->data); return 0; }
  class Node: def __init__(self, data): self.data = data self.next = None def push(head, data): if not head: return Node(data) temp = Node(data) temp.next = head head = temp return head def removeLastNode(head): if head == None: return None if head.next == None: head = None return None second_last = head while(second_last.next.next): second_last = second_last.next second_last.next = None return head if __name__=='__main__': head = None head = push(head, 20) head = push(head, 11) head = push(head, 9) head = push(head, 5) head = push(head, 1) head = removeLastNode(head) while(head): print("{} ".format(head.data), end ="") head = head.next
  Output
  1 5 9 11
  [forminator_quiz id="3679"]
  Space Complexity: O(1), as only temporary variables are bring created.
  So, in this article, we have tried to explain the most efficient approach to remove the last node of a linked list. This problem tests our basic concepts of linked lists, and that is what makes this problem an important one for coding interviews. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.