Delete last n nodes from end of doubly linked list
The problem at hand involves deleting the last n nodes from a doubly linked list. In a doubly linked list, each node contains a data element and two pointers, one pointing to the next node and another pointing to the previous node. The task is to remove the last n nodes from the end of the list.
Problem Statement
Given a doubly linked list and an integer n, the objective is to delete the last n nodes from the end of the list.
Example
Consider the following doubly linked list:
1 <-> 2 <-> 3 <-> 4 <-> 5 <-> 6 <-> 7 <-> 8
If we want to delete the last 5 nodes from the end of the list, the resulting list should be:
1 <-> 2 <-> 3
Idea to Solve
To solve this problem, you need to traverse the list while keeping track of the number of nodes you have visited. Once you have visited n nodes, you can manipulate the pointers of the nodes to remove them from the list.
Pseudocode
function deleteLastN(n):
if head is null or n is less than or equal to 0:
return
temp = head
counter = 0
auxiliary = null
// Check if n nodes exist in the list
while temp is not null and counter < n:
increment counter by 1
move temp to the next node
if counter is greater than or equal to n:
temp = tail
counter = n
// Traverse and delete last n nodes
while tail is not null and counter > 0:
move tail to the previous node
set temp's pointers to null
if temp equals head:
set head to null
decrement counter by 1
if tail is not null:
set tail's next pointer to null
else:
print "Deleted " + n + " nodes are missing"
Algorithm Explanation
- Start by initializing
temp
to thehead
,counter
to 0, andauxiliary
to null. - Traverse the doubly linked list using the
temp
pointer:- Increment the
counter
by 1. - Move
temp
to the next node.
- Increment the
- After traversing, check if
counter
is greater than or equal to n:- If it is, you have visited at least n nodes.
- Initialize
temp
to thetail
andcounter
to n. - Loop through n times and delete nodes from the end:
- Move
tail
to the previous node. - Set
temp
's pointers to null. - If the node being deleted is the
head
, updatehead
to null.
- Move
- Set
tail
's next pointer to null after deletion.
- If
counter
is less than n, print a message indicating that the nodes to be deleted don't exist.
Program List
-
1) Delete N nodes from end of doubly linked list in java
2) Delete N nodes from end of doubly linked list in c++
3) Delete N nodes from end of doubly linked list in c
4) Delete N nodes from end of doubly linked list in golang
5) Delete N nodes from end of doubly linked list c#
6) Delete N nodes from end of doubly linked list in vb.net
7) Delete N nodes from end of doubly linked list in php
8) Delete N nodes from end of doubly linked list in node js
9) Delete N nodes from end of doubly linked list in typescript
10) Delete N nodes from end of doubly linked list python
11) Delete N nodes from end of doubly linked list in ruby
12) Delete N nodes from end of doubly linked list in scala
13) Delete N nodes from end of doubly linked list in swift
14) Delete N nodes from end of doubly linked list in kotlin
Time Complexity
The time complexity of this algorithm is O(n), where n is the number of nodes in the doubly linked list. In the worst case, you might need to traverse the entire list to delete the last n nodes.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment