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

Problem

Submissions

Hints & solutions

Discuss

Insert before tail of Doubly Linked List

Easy

0/40

Average time to solve is 20m

Contributed by

6 upvotes

Asked in company

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 and a value ‘k’, insert a node having value ‘k’ before the tail of the doubly linked list.

Note:

You need not print anything. You’re given the head of the linked list. Return the head of the modified list.

Example:

Input: Linked List: 4 <-> 10 <-> 3 <-> 5 and ‘k’ = 20

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

Explanation: A new node having value ‘k’ = 20 is inserted before the tail of the linked list.

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

Input Format:

The first line contains an integer ‘N’, the number of elements initially in the linked list.
The next line contains ‘N’ numbers, the linked list.
The third line contains an integer ‘k’, the value to be added.

Output format:

Return the head of the modified linked list.

Sample Input 1:

4
4 10 3 5
20

Sample Output 1:

4 10 3 20 5

Explanation Of Sample Input 1 :

A new node having value ‘k’ = 20 is inserted at the end of the linked list.

Sample Input 2 :

0

5

Sample Output 2 :

Explanation Of Sample Input 2 :

The linked list was empty. So the new node is the only node in the modified linked list.

Expected time complexity:

The expected time complexity is O(N).

Constraints:

0 <= ‘N’ <= 100000
1 <= Value in linked list <= 10^9
1 <= ‘k’ <= 10^9

Time limit: 1 second

Approaches (1)

Approach 1

Traversal

The new node will be added before the tail of the linked list, that is, prev element of the current last element. So we will traverse to the second last element, and then add the new node at the new postion. If the linked list is empty, our new node will be the only node in the linked list.

The steps are as follows:

Node * insertAtTail(Node * ‘head’, int ‘k’)

Let ‘newNode’ be a node pointer initialized with value ‘k’.
If ‘head’ is pointing to null:
1. Return ‘newNode’.
If ‘head.next’ is pointing to null:
1. Assign pointers such that ‘newNode’ is the prev element of ‘head’
2. Return ‘newNode’.
Let ‘temp’ be a node pointer pointing to the same node as ‘head’.
While ‘temp’ is not the second last node in the linked list While ‘temp.next.next’ is not pointing to null:
1. ‘temp’ = ‘temp.next’
tail = temp.next
temp.next = newNode
newNode.prev = temp
newNode.next = tail
tail.prev = newNode
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 ‘newNode’ and ‘temp’.

Hence the space complexity is O(1).

(100% EXP penalty)

Insert before tail of Doubly Linked List

Himanshi Pant

Interview problems

C++ easy solution

Node * insertBeforeTail(Node *head, int k) {

// If the linked list is empty

if(head == nullptr){

Node* newNode = new Node(k);

return newNode;

}

//If only one node is present

if(head -> next == nullptr){

return insertBeforeTail(head, k);

}

//Normal case

Node* tail = head;

while(tail->next!=NULL){

tail = tail->next;

}

// Keep track of node before tail using prev

Node* back = tail->prev;

// Create new node with value val

Node* newNode = new Node(k);

newNode -> prev = back;

newNode -> next = tail;

// Join the new node into the doubly linked list

back->next = newNode;

tail->prev = newNode;

// Return the updated linked list

return head;

}

40 views

0 replies

0 upvotes

Shine Shine

Interview problems

EASY|| C++

Node * insertBeforeTail(Node *head, int k) {

// Write your code here

Node *newnode=new Node(k);

if(head==NULL){

return newnode;

}

Node *temp=head;

while(temp->next->next!=NULL){

temp=temp->next;

}

Node *pp=temp->next;

temp->next=newnode;

newnode->next=pp;

newnode->prev=temp;

return head;

}

27 views

0 replies

0 upvotes

Shiya Mer

Interview problems

Why do i get this error?Traceback (most recent call last): File "/box/runner.py", line 65, in runner.execute() File "/box/runner.py", line 54, in execute ans = insertBeforeTail(head, self.k) File "/box/solution.py", line 25, in insertBeforeTail head.prev.next=x AttributeError: 'NoneType' object has no attribute 'next'

def insertBeforeTail(head: Node, k: int) -> Node:

if head==None:

x=Node(k)

return x

if head.next==None:

x=Node(k)

p=x

x.next=head

head.prev=x

return p

x=Node(k)

p=head

while(p.next!=None):

p=p.next

p.prev.next=x

x.prev= p.prev

x.next=p

p.prev=x

return head

24 views

0 replies

0 upvotes

Siddhartha Bharali

Interview problems

Java Solution

public class Solution
 {
     public static Node insertBeforeTail(Node list, int K) {
         // Write your code here
         Node t=new Node(K),curr=list;
         if(list==null) return t;
         while(curr.next!=null) curr=curr.next;
         curr.prev.next=t;
         t.prev=curr.prev;
         t.next=curr;
         curr.prev=t;
         return list;
     }
 }

48 views

0 replies

0 upvotes

Dhananjay Kumar

Interview problems

Java Solution :)

public static Node insertBeforeTail(Node head, int k) {

// Write your code here

Node node = new Node(k);

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

node.next = head;

head = node;

return head;

}

Node temp = head;

while(temp.next != null){

temp = temp.next;

}

node.next = temp;

node.prev = temp.prev;

temp.prev.next = node;

return head;

}

31 views

0 replies

1 upvote

Shreyas G S

Interview problems

CPP EASY SOLUTION

Node * insertBeforeTail(Node *head, int k) {

// Write your code here

if(head==NULL) return new Node(k);

Node* temp=head;

while(temp->next->next){

temp=temp->next;

}

Node* tail=temp->next;

Node* temp1=new Node(k, temp, tail);

temp->next=temp1;

tail->prev=temp1;

return head;

}

112 views

0 replies

0 upvotes

Aditya Kumar Tiwari

Interview problems

C++ || Easy to understand

Node * insertBeforeTail(Node *head, int k) {
    Node *add=new Node(k);
    Node *temp=head;
    if(!head)return add;
    if(!head->next){
        add->next=head;
        head->prev=add;
        return add;
    }
    while(temp->next->next)temp=temp->next;
    Node* back=temp->next;
    temp->next=add;
    add->prev=temp;
    back->prev=add;
    add->next=back;
    return head;
}

60 views

0 replies

1 upvote

Saher Mahtab

Interview problems

Simple Java Solution

public static Node insertBeforeTail(Node list, int K) {

Node temp = list ;

Node newNode = new Node(K) ;

if (list == null) return new Node(K) ;

if (list.next == null){

list.next = newNode ;

newNode.prev = list ;

newNode.next = null ;

return list ;

}

while ( temp.next != null){

temp = temp.next ;

}

Node prev = temp.prev ;

prev.next = newNode ;

newNode.next = temp ;

newNode.prev = prev ;

temp.prev = newNode ;

return list ;

}

39 views

0 replies

1 upvote

Mohd Kaif Khan

Interview problems

Simple C++ Solution

I HAVE EXPLAINED EVERYTHING IN THE CODE READ IT AND IF YOU LIKE THE EXPLANATION THEN PLEASE GIVE ME UPVOTE !!

Node * insertBeforeTail(Node *head, int k) {

// Write your code here

Node* temp = head ; // storing the head so that it don't get tamper

Node* newNode = new Node(k) ; // making a new node for inserting

if ( head == NULL) return new Node(k) ;// base case

if (head->next == NULL){ // this is the case when there is one node only

head->next = newNode ;

newNode->prev = head ;

newNode->next = NULL ;

return head ;

}

while ( temp->next != NULL){

temp = temp->next ; // after this loop your temp will be on the last element

}

Node* prev = temp->prev ; // initializing the prev value just for simplicity

prev->next = newNode ;

newNode->next = temp ;

newNode->prev = prev ;

temp->prev = newNode ;

return head ; // returning the head value

}

100 views

0 replies

1 upvote

Console