Problem

Submissions

Hints & solutions

Discuss

Insert at end of Doubly Linked List

Easy

0/40

Average time to solve is 20m

Contributed by

62 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’ at the end 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 <-> 5 <-> 20

Explanation: A new node having value ‘k’ = 20 is inserted at the end 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 5 20

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 to the end of the linked list, that is, next element of the current last element. So we will traverse to the last element, and then add the new node at the end. 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:
- Return ‘newNode’.
Let ‘temp’ be a node pointer pointing to the same node as ‘head’.
While ‘temp’ is not the last node in the linked list While ‘temp.next’ is not pointing to null:
- ‘temp’ = ‘temp.next’
‘temp.next’ = ‘newNode’
‘newNode.prev’ = ‘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 ‘newNode’ and ‘temp’.

Hence the space complexity is O(1).

(100% EXP penalty)

Insert at end of Doubly Linked List

Bontha Hariswar Reddy

Interview problems

Easy Solution in C++

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

Node *temp = head;

while(temp->next != nullptr){

temp = temp->next;

}

Node *newNode = new Node(k);

newNode->prev = temp;

newNode->next = nullptr;

temp->next = newNode;

return head;

37 views

0 replies

0 upvotes

akarshan gupta

Interview problems

EASY C++ SOLUTION

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

// Write your code here

if(head==NULL){

return new Node(k);

}

Node* temp=head;

while(temp->next!=NULL){

temp=temp->next;

}

Node* newnode=new Node(k,temp,nullptr);

temp->next=newnode;

return head;

}

programming

13 views

0 replies

0 upvotes

Saurav Kumar

Interview problems

Best and optimised C++ solution using Doubly Linked List

Following is the class structure of the Node class

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

Node*s=new Node(k);

if(head == NULL){

return s ;

}

Node* tail=head;

while(tail->next!=nullptr){

tail=tail->next;

}

Node*NewTail=new Node(k,tail,nullptr);

tail->next=NewTail;

return head;

}

14 views

0 replies

1 upvote

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 insertAtTail(Node list, int K) {

//create a new node

Node node=new Node(K);

if(list==null){

list=node;

return list;

}

//link the node

Node temp=list;

//find out the last node

while(temp.next!=null){

temp=temp.next;

}

//link the new node with last node

temp.next=node;

node.prev=temp;

return list;

}

java

93 views

0 replies

0 upvotes

Gyanesh Kumar

Interview problems

java

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

Node newNode=new Node(K);

// creating a node with data K ;

if(list==null){ // if list is empty we can simply return our newNode;

return newNode;

}

Node curr=list;

// for inserting new node we have to reach at the end of the list;

while(curr.next!=null){

curr=curr.next;

}

//now we have reach the tail off the node,here we have to create all link with newNode;

curr.next=newNode; //creating link with newNode;

newNode.prev=curr; //creating link with prev node;

return list;

}

51 views

0 replies

0 upvotes

Nitish kumar

Interview problems

Java Solution

public class Solution

{

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

// Write your code here

Node newnode = new Node(K);

if(list == null){

return newnode;

}

Node curr = list;

while(curr.next != null){

curr = curr.next;

}

curr.next = newnode;

newnode.prev = curr;

return list;

}

13 views

0 replies

0 upvotes

Divyanshu Narayan

Interview problems

python solution

#comment for detailed explation

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

# Write your code here

temp=head

new=Node(k)

if head==None:

return new

while(temp.next!=None):

temp=temp.next

temp.next=new

temp.prev=temp

return head

32 views

0 replies

0 upvotes

Vivek Kamdi

Interview problems

C++ Solution

Node * insertAtTail(Node *head, int k) {
    Node*nn= new Node(k);
    Node*temp=head;
    if(head == nullptr) return nn;
    while(temp->next!=nullptr) temp=temp->next;
    nn->prev=temp;
    temp->next=nn;

    return head;
}

400 views

0 replies

0 upvotes

Vivek Kumar Sahu

Interview problems

Java Solution

public class Solution

{

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

// Write your code here

Node newNode = new Node(K);

if(list==null){

return newNode;

}

Node temp = list;

while(temp.next!=null){

temp=temp.next;

}

temp.next=newNode;

newNode.prev = temp;

return list;

}

80 views

0 replies

0 upvotes

Tanishq Vasani

Interview problems

beginner java easy solution

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

// Write your code here

Node k = new Node(K,null,null);

if(list==null)

{

return k;

}

Node temp = list;

while(temp.next!=null){

temp=temp.next;

}

temp.next=k;

k.prev=temp;

return list;

}

31 views

0 replies

0 upvotes

Console