# Linked List

## Problem Statement: **Clone a linked list with next and random pointer**

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 = 2

value = {1,2,3,4}

pairs = {{1,2},{2,4}}

**Output: **1

Explanation: In this test case, there

re 4 nodes in linked list. Among these

4 nodes, 2 nodes have arbit pointer

set, rest two nodes have arbit pointer

as NULL. Second line tells us the value

of four nodes. The third line gives the

information about arbitrary pointers.

The first node arbit pointer is set to

node 2. The second node arbit pointer

is 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*cur = head;

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 = 4

value = {{1,2,3},{4 5},{5 6},{7,8}}

**Output: **1 2 3 4 5 5 6 7 8

Explanation:

The test case has 4 sorted linked

list of size 3, 2, 2, 2

1st list 1 -> 2-> 3

2nd list 4->5

3rd list 5->6

4th list 7->8

The merged list will be

1->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)

pq.add(arr[i]);

// 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’

pq.add(top.next);

// if final merged list is empty

if (head == null) {

head = top;

// 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

return head;

}

}

**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->4

Output : 79464Input : 3->2->1

1->2

Output : 38521) Initialize a variable to zero

2) Start traversing the linked list

3) Add the value of first node to this variable

4) 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