Delete Last Node of Linked List

Problem Statement: Given a Singly LinkedList, Delete the Last Node in the LinkedList.

Examples:

Example 1:
Input: List = 10->20->30->40->null
Output: 10->20->30->null
Explanation: Deleted the last node of the linked list.

Example 2:
Input: List = 100->200->300->null
Output: 100->200->null
Explanation: Deleted the last node of the linked list

Solution :

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Approach:

Deletion of Last Node in Singly LinkedList is 3 step process.

Step 1: Find the last Node and second Last Node of the LinkedList. To Find the Nodes, take two ListNode pointers let’s say prev, curr. Initially curr points to the head and prev points to the Null. Move the curr and prev pointers ahead in the LinkedList until the curr reaches the last Node.

How do we know which is Node is the last node?

Next of the Last Node points to null, If for any node it’s next is null, then it is the last node in LinkedList.

After step1 curr points to the last node and prev points to the second Last Node in LinkedList.

Step 2: We need to remove the Last node, so break the link connecting the LastNode with List. In order to break the link, make prev→next = NULL

Step 3: Delete the curr Node, which means the Last Node.

Final LinkedList after Deleting Last Node.

Code:

C++ Code

#include <bits/stdc++.h>

using namespace std;

class ListNode {
  public:
    int val;
  ListNode * next;
  ListNode(int x) {
    val = x;
    next = nullptr;
  }
};

ListNode * head, * tail; // head and tail of the LinkedList

void PrintList() // Function to print the LinkedList
{
  ListNode * curr = head;
  for (; curr != nullptr; curr = curr -> next)
    cout << curr -> val << "-->";
  cout << "null" << endl;
}

void InsertatLast(int value) // Function for creating a LinkedList
{

  ListNode * newnode = new ListNode(value);
  if (head == nullptr)
    head = newnode, tail = newnode;
  else
    tail = tail -> next = newnode;
}

void DeleteLast() {
  if (head == nullptr)
    cout << "There are no nodes to delete in LinkedList" << endl;

  // If there is single node, delete that and make head point to null
  if (head -> next == nullptr) {
    delete head;
    head = nullptr;
  } else {

    // step1: Finding First and Second Last Node in LinkedList

    ListNode * curr = head, * prev = nullptr;
    while (curr -> next != nullptr) {
      prev = curr;
      curr = curr -> next;
    }

    // Step2 : Pointing prev->next to nullptr

    prev -> next = nullptr;

    // Step3 :Deleting the LastNode

    delete curr;
  }
}

int main() {
  InsertatLast(10);
  InsertatLast(20);
  InsertatLast(30);
  InsertatLast(40);
  cout << "LinkedList before Deleting Last Node : " << endl;
  PrintList();
  DeleteLast();
  cout << "LinkedList after Deleting Lastt Node : " << endl;
  PrintList();
  return 0;
}

Output:

LinkedList before Deleting Last Node :
10–>20–>30–>40–>null
LinkedList after Deleting Lastt Node :
10–>20–>30–>null

Time Complexity: O(N) Because we are traversing the LinkedList to find out the first and second Last Nodes in LinkedList. N is the No of Nodes in LinkedList.

Space Complexity: O(1) We are not using any extra space.

Java Code

import java.util.*;

class ListNode {

  int val;
  ListNode next;
  ListNode(int x) {
    val = x;
    next = null;
  }
}
class TUF {

  static ListNode head, tail; // head and tail of the LinkedList

  static void PrintList() // Function to print the LinkedList
  {
    ListNode curr = head;
    for (; curr != null; curr = curr.next)
      System.out.print(curr.val + "-->");
    System.out.println("null");
  }

  static void InsertatLast(int value) // Function for creating a LinkedList
  {

    ListNode newnode = new ListNode(value);
    if (head == null) {
      head = newnode;
      tail = newnode;
    } else
      tail = tail.next = newnode;
  }

  static void DeleteLast() {
    if (head == null)
      System.out.println("There are no nodes to delete in LinkedList");

    // If there is single node, delete that and make head point to null
    if (head.next == null) {
      head = null;
    } else {

      // step1: Finding First and Second Last Node in LinkedList

      ListNode curr = head, prev = null;
      while (curr.next != null) {
        prev = curr;
        curr = curr.next;
      }

      // Step2 : Pointing prev->next to nullptr

      prev.next = null;

    }
  }

  public static void main(String args[]) {
    InsertatLast(10);
    InsertatLast(20);
    InsertatLast(30);
    InsertatLast(40);
    System.out.println("LinkedList before Deleting Last Node : ");
    PrintList();
    DeleteLast();
    System.out.println("LinkedList after Deleting Lastt Node : ");
    PrintList();
  }
}

Output:

LinkedList before Deleting Last Node :
10–>20–>30–>40–>null
LinkedList after Deleting Lastt Node :
10–>20–>30–>null

Time Complexity: O(N) Because we are traversing the LinkedList to find out the first and second Last Nodes in LinkedList. N is the No of Nodes in LinkedList.

Space Complexity: O(1) We are not using any extra space.

Special thanks to SaiSri Angajala for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article