You are given a special linked list with N nodes where each node has a next pointer pointing to its next node. You are also given M random pointers , where you will be given M number of pairs denoting two nodes a and b

i.e. a->arb = b.

`Input:N = 4, M = 2value = {1,2,3,4}pairs = {{1,2},{2,4}}Output: 1Explanation: In this test case, therere 4 nodes in linked list.  Among these4 nodes,  2 nodes have arbit pointerset, rest two nodes have arbit pointeras NULL. Second line tells us the valueof four nodes. The third line gives theinformation about arbitrary pointers.The first node arbit pointer is set tonode 2.  The second node arbit pointeris set to node 4.`

Sol:

class Clone {
//Function to clone a linked list with next and random pointer.
Node copyList(Node head) {
Node cur = head;
Node temp;

//Make clone node

while(cur!=null) {
temp = cur.next; //Storing next value of cur into temp
cur.next = new Node(cur.data); // Make new node and storing value of cur as clone
cur.next.next = temp; // point Clone Node to temp
cur = temp; // point cur to temp for further iteration
}

//Make arbitrary Pointer value
while(cur != null) {
cur.next.arb = cur.arb!=null ? cur.arb.next : null;

//Point clone.arb -> search for original.arb and point to Original.arb. Next if present otherwise null

cur = cur.next.next; //Move original to next original
}

//Make Clone and Original Linked List

Node original = head;
Node clone = head. Next;
temp = clone; // As we will return temp at last it will act as HEAD
while(original!=null && clone!=null) {
ori.next = original.next.next;
clone. Next = clone. Next!=null ? clone.next.next : null;
original = ori.next;
clone = clone. Next;
}
return temp;
}
}

Expected Time Complexity : O(n)
Expected Auxiliary Space : O(1)

## Problem Statement: Merge K sorted linked lists (V.V.V.I)

Given K sorted linked lists of different sizes. The task is to merge them in such a way that after merging they will be a single sorted linked list.

`Input:K = 4value = {{1,2,3},{4 5},{5 6},{7,8}}Output: 1 2 3 4 5 5 6 7 8Explanation:The test case has 4 sorted linked list of size 3, 2, 2, 21st    list     1 -> 2-> 32nd   list      4->53rd    list      5->64th    list      7->8The merged list will be1->2->3->4->5->5->6->7->8.`

class Solution
{
//Function to merge K sorted linked list.
Node mergeKList(Node[]arr, int K)
{
Node head = null, last = null;

// priority_queue ‘pq’ implemeted
// as min heap with the
// help of ‘compare’ function

Priority_queue<Node> pq
= new Priority_queue<>(
new Comparator<Node>() {
public int compare(Node a, Node b)
{
return a. Data — b.data;
}
});

// push the head nodes of all
// the k lists in ‘pq’
for (int i = 0; I < K; I++)
if (arr[i] != null)

// loop till ‘pq’ is not empty
while (!pq.isEmpty()) {
// get the top element of ‘pq’
Node top = pq.peek();
pq.remove();

// check if there is a node
// next to the ‘top’ node
// in the list of which ‘top’
// node is a member
if (top. Next != null)
// push the next node in ‘pq’

// if final merged list is empty
if (head == null) {
// points to the last node so far of
// the final merged list
last = top;
}
else {
// insert ‘top’ at the end
// of the merged list so far
last. Next = top;

// update the ‘last’ pointer
last = top;
}
}
// head node of the required merged list
}
}

• Time Complexity: O( n * k * log k).
Insertion and deletion in a Min Heap requires log k time. So the Overall time complexity is O( n * k * log k)
• Auxiliary Space: O(k).
k is the space required to store the priority queue

## Multiply two numbers represented by Linked Lists

Given two numbers represented by linked lists, write a function that returns the multiplication of these two linked lists.

Examples:

`Input : 9->4->6        8->4Output : 79464Input : 3->2->1        1->2Output : 38521) Initialize a variable to zero2) Start traversing the linked list3) Add the value of first node to this variable4) From the second node, multiply the variable by 10   and also take modulus of this value by 10^9+7   and then add the value of the node to this    variable.5) Repeat step 4 until we reach the last node of the list.`

class Sol{
public long multiplyTwoLists(Node l1,Node l2){
long N = 1000000007; //As some time value can be large to store
long num1 = 0, num2 = 0;

while (l1 != null || l2 != null){

if(l1 != null){
num1 = ((num1)*10)%N + l1.data; // [0*10+9]%N ->Iteration1

//[9*10+4]%N ->Iteration2 …

l1 = l1.next;
}
//Will do same for l2
if(l2 != null)
{
num2 = ((num2)*10)%N + l2.data;
l2 = l2.next;
}

}

//At the end we multiply two values
return ((num1*num2)%N);
}
}

Thanks

--

--