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