Top List List

How do you delete a node from the end of a linked list?

Remove last node of the linked list

Given a linked list, the task is to remove the last node of the linked list and update the head pointer of the linked list.

Examples:

Input: 1 -> 2 -> 3 -> 4 -> 5 -> NULL Output: 1 -> 2 -> 3 -> 4 -> NULL Explanation: The last node of the linked list is 5, so 5 is deleted. Input: 2 -> 4 -> 6 -> 8 -> 33 -> 67 -> NULL Output: 2 -> 4 -> 6 -> 8 -> 33 -> NULL Explanation: The last node of the linked list is 67, so 67 is deleted.

Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Approach: To delete the last node of a linked list, find the second last node and make the next pointer of that node null.

Algorithm:

1. If the first node is null or there is only one node, then they return null.

if headNode == null then return null if headNode.nextNode == null then free head and return null

2. Create an extra space secondLast, and traverse the linked list till the second last node.

while secondLast.nextNode.nextNode != null secondLast = secondLast.nextNode

3. delete the last node, i.e. the next node of the second last node delete[secondLast.nextNode], and set the value of the next second-last node to null.

Implementation:

C++

// CPP program to remove last node of

// linked list.

#include

using namespace std;

/* Link list node */

struct Node {

int data;

struct Node* next;

};

/* Function to remove the last node

of the linked list */

Node* removeLastNode[struct Node* head]

{

if [head == NULL]

return NULL;

if [head->next == NULL] {

delete head;

return NULL;

}

// Find the second last node

Node* second_last = head;

while [second_last->next->next != NULL]

second_last = second_last->next;

// Delete last node

delete [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 = new Node;

new_node->data = new_data;

new_node->next = [*head_ref];

[*head_ref] = new_node;

}

// Driver code

int main[]

{

/* Start with the empty list */

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 [Node* temp = head; temp != NULL; temp = temp->next]

cout data 3 -> 1 -> 7 -> NULL, N = 1
Output:
The created linked list is:
2 3 1 7
The linked list after deletion is:
2 3 1

Input: 1 -> 2 -> 3 -> 4 -> NULL, N = 4
Output:
The created linked list is:
1 2 3 4
The linked list after deletion is:
2 3 4

Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Intuition:

Lets K be the total nodes in the linked list.

Observation : The Nthnode from the end is [K-N+1]th node from the beginning.

So the problem simplifies down to that we have to find [K-N+1]th node from the beginning.

One way of doing it is to find the length [K] of the linked list in one pass and then in the second pass move [K-N+1] step from the beginning to reach the Nthnode from the end.
To do it in one pass. Let’s take the first pointer and move N step from the beginning. Now the first pointer is [K-N+1] steps away from the last node, which is the same number of steps the second pointer require to move from the beginning to reach the Nth node from the end.

Approach:

Take two pointers; the first will point to the head of the linked list and the second will point to the Nth node from the beginning.
Now keep incrementing both the pointers by one at the same time until the second is pointing to the last node of the linked list.
After the operations from the previous step, the first pointer should point to the Nth node from the end now. So, delete the node the first pointer is pointing to.

Below is the implementation of the above approach:

C++

// C++ implementation of the approach

#include

using namespace std;

class LinkedList

{

public:

// Linked list Node

class Node

{

public:

int data;

Node* next;

Node[int d]

{

data = d;

next = NULL;

}

};

// Head of list

Node* head;

// Function to delete the nth node from

// the end of the given linked list

Node* deleteNode[int key]

{

// We will be using this pointer for holding

// address temporarily while we delete the node

Node *temp;

// First pointer will point to

// the head of the linked list

Node *first = head;

// Second pointer will point to the

// Nth node from the beginning

Node *second = head;

for [int i = 0; i < key; i++]

{

// If count of nodes in the given

// linked list is next == NULL]

{

// If count = N i.e.

// delete the head node

if [i == key - 1]{

temp = head;

head = head->next;

free [temp];

}

return head;

}

second = second->next;

}

// Increment both the pointers by one until

// second pointer reaches the end

while [second->next != NULL]

{

first = first->next;

second = second->next;

}

// First must be pointing to the

// Nth node from the end by now

// So, delete the node first is pointing to

temp = first->next;

first->next = first->next->next;

free [temp];

return head;

}

// Function to insert a new Node

// at front of the list

Node* push[int new_data]

{

Node* new_node = new Node[new_data];

new_node->next = head;

head = new_node;

return head;

}

// Function to print the linked list

void printList[]

{

Node* tnode = head;

while [tnode != NULL]

{

cout data] next;

}

};

// Driver code

int main[]

{

LinkedList* llist = new LinkedList[];

llist->head = llist->push[7];

llist->head = llist->push[1];

llist->head = llist->push[3];

llist->head = llist->push[2];

cout printList[];

int N = 1;

llist->head = llist->deleteNode[N];

cout printList[];

}

// This code is contributed by Arnab Kundu

Java

// Java implementation of the approach

class LinkedList {

// Head of list

Node head;

// Linked list Node

class Node {

int data;

Node next;

Node[int d]

{

data = d;

next = null;

}

// Function to delete the nth node from

// the end of the given linked list

void deleteNode[int key]

{

// First pointer will point to

// the head of the linked list

Node first = head;

// Second pointer will point to the

// Nth node from the beginning

Node second = head;

for [int i = 0; i < key; i++] {

// If count of nodes in the given

// linked list is next = head
2] Then we will use the recursion stack to keep track of elements that are being pushed in recursion calls.
3] While popping the elements from recursion stack, we will decrement the N[position of target node from the end of linked list] i.e, N = N-1.
4] When we reach [N==0] that means we have reached at the target node,
5] But here is the catch, to delete the target node we require its previous node,
6] So we will now stop when [N==-1] i.e, we reached the previous node.
7] Now it is very simple to delete the node by using previousNode->next = previousNode->next->next.

C++

// C++ implementation of the approach

// Code is contributed by Paras Saini

#include

using namespace std;

class LinkedList {

public:

int val;

LinkedList* next;

LinkedList[]

{

this->next = NULL;

this->val = 0;

}

LinkedList[int val]

{

this->next = NULL;

this->val = val;

}

LinkedList* addNode[int val]

{

if [this == NULL] {

return new LinkedList[val];

}

else {

LinkedList* ptr = this;

while [ptr->next] {

ptr = ptr->next;

}

ptr->next = new LinkedList[val];

return this;

}

void removeNthNodeFromEndHelper[LinkedList* head,

int& n]

{

if [!head]

return;

// Adding the elements in the recursion

// stack

removeNthNodeFromEndHelper[head->next, n];

// Popping the elements from recursion stack

n -= 1;

// If we reach the previous of target node

if [n == -1]{

LinkedList* temp = head->next;

head->next = head->next->next;

free [temp];

}

LinkedList* removeNthNodeFromEnd[int n]

{

// return NULL if we have NULL head or only

// one node.

if [!this or !this->next]

return NULL;

// Create a dummy node and point its next to

// head.

LinkedList* dummy = new LinkedList[];

dummy->next = this;

// Call function to remove Nth node from end

removeNthNodeFromEndHelper[dummy, n];

// Return new head i.e, dummy->next

return dummy->next;

}

void printLinkedList[]

{

if [!this] {

cout addNode[3];

head = head->addNode[4];

head = head->addNode[5];

head->printLinkedList[]; // Print: 1 2 3 4 5

head = head->removeNthNodeFromEnd[2];

printOutput[head]; // Output: 1 2 3 5

}

void testCase2[]

{

// Important Edge Case, where linkedList [1]

// and n=1,

LinkedList* head = new LinkedList[1];

head->printLinkedList[]; // Print: 1

head = head->removeNthNodeFromEnd[2];

printOutput[head]; // Output: Empty Linked List

}

void testCase3[]

{

LinkedList* head = new LinkedList[1];

head = head->addNode[2];

head->printLinkedList[]; // Print: 1 2

head = head->removeNthNodeFromEnd[1];

printOutput[head]; // Output: 1

}

public:

void executeTestCases[]

{

testCase1[];

testCase2[];

testCase3[];

}

};

int main[]

{

TestCase testCase;

testCase.executeTestCases[];

return 0;

}

Output 1 2 3 4 5 1 2 3 5 1 Empty Linked List 1 2 1

Two Pointer Approach – Slow and Fast Pointers

This problem can be solved by using two pointer approach as below:

Take two pointers – fast and slow. And initialize their values as head node
Iterate fast pointer till the value of n.
Now, start iteration of fast pointer till the None value of the linked list. Also, iterate slow pointer.
Hence, once the fast pointer will reach to the end the slow pointer will reach the node which you want to delete.
Replace the next node of the slow pointer with the next to next node of the slow pointer.

Python

class Node:

def __init__[self, data]:

self.data = data

self.next = None

class LinkedList:

def __init__[self]:

self.head = None

def push[self, data]:

new_node = Node[data]

new_node.next = self.head

self.head = new_node

def display[self]:

temp = self.head

while temp != None:

print[temp.data]

temp = temp.next

def deleteNthNodeFromEnd[self, head, n]:

fast = head

slow = head

for _ in range[n]:

fast = fast.next

if not fast:

return head.next

while fast.next:

fast = fast.next

slow = slow.next

slow.next = slow.next.next

return head

if __name__ == '__main__':

l = LinkedList[]

l.push[5]

l.push[4]

l.push[3]

l.push[2]

l.push[1]

print['***** Linked List Before deletion *****']

l.display[]

print['************** Delete nth Node from the End *****']

l.deleteNthNodeFromEnd[l.head, 2]

print['*********** Linked List after Deletion *****']

l.display[]

Output ***** Linked List Before deletion ***** 1 2 3 4 5 ************** Delete nth Node from the End ***** *********** Linked List after Deletion ***** 1 2 3 5

Time complexity: O[n]

Article Tags :

Linked List

Delete a Linked List

Traversal

Practice Tags :

Linked List

Traversal

Read Full Article

Deletion in singly linked list at the end

There are two scenarios in which, a node is deleted from the end of the linked list.

There is only one node in the list and that needs to be deleted.
There are more than one node in the list and the last node of the list will be deleted.

Program to delete a node from the end of the singly linked list

Explanation

In this program, we will create a singly linked list and delete a node from the end of the list. To accomplish this task, we first find out the second last node of the list. Then, make second last node as the new tail of the list. Then, delete the last node of the list.

In the above example, Node was the tail of the list. Traverse through the list to find out the second last node which in this case is node 4. Make node 4 as the tail of the list. Node 4's next will point to null.

Algorithm

Create a class Node which has two attributes: data and next. Next is a pointer to the next node in the list.
Create another class DeleteEnd which has two attributes: head and tail.
addNode[] will add a new node to the list:
1. Create a new node.
2. It first checks, whether the head is equal to null which means the list is empty.
3. If the list is empty, both head and tail will point to a newly added node.
4. If the list is not empty, the new node will be added to end of the list such that tail's next will point to a newly added node. This new node will become the new tail of the list.
DeleteFromEnd[] will delete a node from the end of the list:
1. It first checks whether the head is null [empty list] then, display the message "List is empty" and return.
2. If the list is not empty, it will check whether the list has only one node.
3. If the list has only one node, it will set both head and tail to null.
4. If the list has more than one node then, traverse through the list till node current points to second last node in the list.
5. Node current will become the new tail of the list.
6. Node next to current will be made null to delete the last node.
display[] will display the nodes present in the list:
1. Define a node current which will initially point to the head of the list.
2. Traverse through the list till current points to null.
3. Display each node by making current to point to node next to it in each iteration.