Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Problem

Submissions

Hints & solutions

Discuss

Delete Last Node of a Doubly Linked List

Easy

0/40

Average time to solve is 20m

Contributed by

45 upvotes

Problem statement

A doubly-linked list is a data structure that consists of sequentially linked nodes, and the nodes have reference to both the previous and the next nodes in the sequence of nodes.

Given a doubly-linked list, delete the node at the end of the doubly linked list.

Note:

You need not print anything. You’re given the head of the linked list, just return the head of the modified list.

Example:

Input: Linked List:  4 <-> 10 <-> 3 <-> 5 <-> 20

Output: Modified Linked List: 4 <-> 10 <-> 3 <-> 5

Explanation: The last node having ‘data’ = 20 is removed from the linked list.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains an integer ‘N’, the number of elements in the linked list.
The next line contains ‘N’ numbers, the linked list.

Output format:

Return the modified linked list.

Sample Input 1:

5
4 10 3 5 20

Sample Output 1:

4 10 3 5 NULL

Explanation Of Sample Input 1 :

The last node having ‘data’ = 20 is removed from the linked list.

Sample Input 2 :

1
5

Sample Output 2 :

NULL

Explanation Of Sample Input 2 :

The linked list has only one node, so the modified linked list is empty.

Expected time complexity :

The expected time complexity is O(N).

Constraints:

1 <= ‘N’ <= 100000
1 <= Data of a node in linked list <= 10^9

Time limit: 1 second

Approaches (1)

Approach 1

Traversal

We will first traverse to the last element. If we remove the last node while pointing at it, the deallocated memory might be used by another process, and we will lose our remaining linked list. Also, we have to make the second last node point towards null.

Store the last node in a temporary variable, move to the previous node, that is, the second last node, remove the last node stored in the temporary variable and manage the values of other pointers.

Note that If the linked list is empty or it has only 1 node, our modified linked list is empty.

The steps are as follows:

Node * deleteLastNode(Node * ‘head’) {

If ‘head’ is pointing to null:
- Return null.
If ‘head.next’ is pointing to null, that is, ‘head’ is the only node in the linked list:
- Free the memory allocated to ‘head’.
- Return null.
Let ‘curr’ be a node pointer pointing to the same node as ‘head’.
While ‘curr’ is not the last node in the linked list / While ‘curr.next’ is not pointing to null:
- ‘curr’ = ‘curr.next’
Let ‘temp’ be a node pointer pointing to the same node as ‘curr’.
‘curr’ = ‘curr.prev’
‘curr.next’ = null
Free the memory allocated to ‘temp’.
Return ‘head’.

Time Complexity

O(N), Where 'N' is the size of the linked list.

To reach the end of the linked list, we have to traverse through all the nodes of the linked list.

Hence the time complexity is O(N).

Space Complexity

O(1)

We are not using any extra space except ‘curr’ and ‘temp’.

Hence the space complexity is O(1).

(100% EXP penalty)

Delete Last Node of a Doubly Linked List

Atul Singhal

Interview problems

Easy solution in c++

Node * deleteLastNode(Node *head) {

// Write your code here

int cnt=0;

Node* temp=head;

while(temp->next!=NULL){

temp=temp->next;

cnt++;

}

if(cnt<=0) return NULL;

temp->prev->next=NULL;

delete temp;

return head;

}

17 views

0 replies

0 upvotes

Nilesh Sunil Kudale

Interview problems

Easy Peasy Solution By NK

Node * deleteLastNode(Node *head) {

// Write your code here

if(head==NULL || head->next==NULL){

return NULL;

}

Node* temp=head;

Node* prev=NULL;

while(temp->next!=NULL){

prev=temp;

temp=temp->next;

}

prev->next=NULL;

temp->prev=NULL;

delete temp;

return head;

}

17 views

0 replies

1 upvote

Bontha Hariswar Reddy

Interview problems

Basic Code in C++

Node *deleteLastNode(Node *head) {

if (head == nullptr || head->next == nullptr)

return nullptr;

Node *temp = head;

while (temp->next != nullptr) {

temp = temp->next;

}

Node *back = temp->prev;

back->next = nullptr;

temp->prev = nullptr;

return head;

}

19 views

0 replies

0 upvotes

Nilesh Jaiswal

Interview problems

python solution

class Node:
    def __init__(self, data=0, next=None, prev=None):
        self.data = data
        self.next = next
        self.prev = prev


# Do not change code above.


def deleteLastNode(head: Node) -> Node:
    if head is None or head.next is None:
        return None
    
    else:
        last_node = None
        current = head
        while current.next is not None:
            last_node = current
            current = current.next
        
        last_node.next = None
        current.prev = None

        return head

10 views

0 replies

0 upvotes

SHRAMAN PAUL

Interview problems

💡 Best C++ solution for Beginners!!!

/**

* Definition of doubly linked list:

* struct Node {

* int data;

* Node *prev;

* Node *next;

* Node() : data(0), prev(nullptr), next(nullptr) {}

* Node(int val) : data(val), prev(nullptr), next(nullptr) {}

* Node(int val, Node *p, Node *n) : data(val), prev(p), next(n) {}

* };

*************************************************************************/

Node * deleteLastNode(Node *head) {

Node *temp=head; //create a temp node on the head

while(temp){ //will traverse until the last node

if(temp->next==NULL){

if(temp->prev==NULL||temp==NULL){ //if 1 element is present or none is present

head=NULL;

} else {

temp->prev->next = NULL;//first set the prev to next i.e. the link from its previos node to null

temp->prev = NULL; //then set the prev node from the last node to null

}

temp=temp->next; //iterate through each step

}

return head;

}

50 views

0 replies

0 upvotes

Pikachu

Interview problems

c++

Node * deleteLastNode(Node *head) {

if(head==nullptr || head->next==nullptr){

return nullptr;

}

Node*temp=head;

while(temp->next!=nullptr){

temp=temp->next;

}

Node*newtail=temp->prev;

newtail->next=nullptr;

temp->prev=nullptr;

delete temp;

return head;

}

31 views

0 replies

0 upvotes

Mahima Chauhan

Interview problems

best and optimised Java solution

/****************************************************************

Following is the class structure of the Node class:

class Node {

public int data;

public Node next;

public Node prev;

Node()

{

this.data = 0;

this.next = null;

this.prev = null;

}

Node(int data)

{

this.data = data;

this.next = null;

this.prev = null;

}

Node(int data, Node next, Node prev)

{

this.data = data;

this.next = next;

this.prev = prev;

}

};

*****************************************************************/

public class Solution

{

public static Node deleteLastNode(Node head) {

if(head==null || head.next==null)return null;

//create a temp node

Node temp=head;

//move it to the second last node

while(temp.next.next!=null)temp=temp.next;

//point the next of second last to null;

temp.next=null;

return head;

}

47 views

0 replies

0 upvotes

Gyanesh Kumar

Interview problems

java

public class Solution

{

public static Node deleteLastNode(Node head) {

// if there is null node or one node given

if(head==null || head.next==null){

return null;

}

Node tail=head; // we are assigning the tail to head and traversing it to the end;

while(tail.next!=null){

tail=tail.next;

}

// after reaching at the tail we have to cut all the links between tail and 2nd last node;

Node prevNode=tail.prev; // here 2nd last node becomes prevNode;

tail.prev=null; //removing prev link with prevNode;

prevNode.next=null; // removing next link with tail node;

return head;

}

39 views

0 replies

0 upvotes

Chavva Chandrika Reddy

Interview problems

all test cases passed c++ solution

/**

* Definition of doubly linked list:

* struct Node {

* int data;

* Node *prev;

* Node *next;

* Node() : data(0), prev(nullptr), next(nullptr) {}

* Node(int val) : data(val), prev(nullptr), next(nullptr) {}

* Node(int val, Node *p, Node *n) : data(val), prev(p), next(n) {}

* };

*************************************************************************/

Node * deleteLastNode(Node *head) {

// Write your code here

if(head==nullptr || head->next==nullptr){

return nullptr;

}

Node* tail=head;

while(tail->next!=nullptr){

tail=tail->next;

}

Node* nn=tail->prev;

nn->next=nullptr;

tail->prev=nullptr;

free(tail);

return head;

}

96 views

0 replies

0 upvotes

Abhyudaya Dubey

Interview problems

Delete Last Node of a Doubly Linked List

Node * deleteLastNode(Node *head) {

// Write your code here

Node* tail=head;

while(tail->next!=NULL){

tail=tail->next;

}

if(head==tail){

Node* temp=head;

head=NULL;

tail=NULL;

delete temp;

}

else{

Node* temp=tail->prev;

temp->next=NULL;

tail->prev=NULL;

delete tail;

tail=temp;

}

return head;

}

74 views

0 replies

0 upvotes

Console