Skip to main content

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

  1. Start by initializing temp to the head, counter to 0, and auxiliary to null.
  2. Traverse the doubly linked list using the temp pointer:
    • Increment the counter by 1.
    • Move temp to the next node.
  3. 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 the tail and counter 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, update head to null.
    • Set tail's next pointer to null after deletion.
  4. If counter is less than n, print a message indicating that the nodes to be deleted don't exist.

Program List

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.





Comment

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