Linked List

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 : 79464
Input : 3->2->1
1->2
Output : 3852
1) 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

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store