Topic: Linked List
Questions Successfully Completed: 2
1) Insert in Middle of Linked List | Easy |
2) Doubly linked list Insertion at a given position | Easy |
Insert in Middle of Linked List
Time Complexity: O(N)
Space Complexity: O(1)
Question
Input: LinkedList = 1->2->4 key = 3 Output: 1 2 3 4 Explanation: The new element is inserted after the current middle element in the linked list.
class Node {
int data;
Node next;
public Node(int data){
this.data = data;
this.next = null;
}
}
class Solution {
public Node insertInMid(Node head, int data){
Node gq = new Node(data);
Node nm = head;
int count = 0;
while(nm!=null){
count++;
nm = nm.next;
}
int half = count/2;
if(count%2==0){
half = half -1;
}
nm=head;
while(half>0){
nm=nm.next;
half--;
}
gq.next = nm.next;
nm.next=gq;
return head;
}
}
Doubly linked list Insertion at a given position
Time Complexity: O(N)
Space Complexity: O(1)
Question
Input1: LinkedList: 2<->4<->5 p = 2, x = 6 Output: 2 4 5 6 Explanation: p = 2, and x = 6. So, 6 is inserted after p, i.e, at position 3 (0-based indexing). Input 2: LinkedList: 1<->2<->3<->4 p = 0, x = 44 Output: 1 44 2 3 4 Explanation: p = 0, and x = 44 . So, 44 is inserted after p, i.e, at position 1 (0-based indexing).
class Node
{
int data;
Node next;
Node prev;
Node(int data)
{
this.data = data;
next = prev = null;
}
}
void addNode(Node head_ref, int pos, int data)
{
Node e = new Node(data);
Node dd = head_ref;
for(int i=0;i<pos;i++){
dd=dd.next;
}
// adding at last
if(dd.next == null){
dd.next = e;
e.prev = dd;
e.next = null;
}
// adding at any position
else{
e.next = dd.next;
dd.next.prev = e;
e.prev = dd;
dd.next = e;
}
}
Thank you for reading :)