Questions discussed

## Problem Statement

Implement Linked list and write reverse() method that reverse the list in-place.

Find the problem on Leetcode $$\to$$

### Approach

Using variables we'll reverse the list in $$O(N)$$ time and $$O(1)$$ space.

### C++ Code for Linked List

#include <iostream>
#include <vector>
using namespace std;

template <class T>
class Node {
public:
T data;
Node<T>* next;

Node(T value) {
data = value;
next = nullptr;
}
};

template <class T>
private:
int size;
public:
Node<T>* end;

end = nullptr;
}

// delete each and every node that is allocated
}
}

void push_front(T value) {
Node<T>* newNode = new Node<T>(value);

if (not head and not end) {
end = newNode;
} else {
}

size++;
}

void push_back(T value) {
Node<T>* newNode = new Node<T>(value);

if (not head and not end) {
end = newNode;
} else {
end->next = newNode;
end = newNode;
}
}

void out() const{
while (traveller) {
cout << traveller->data << " ";
traveller = traveller->next;
}
}

T front() {
}

T back() {
return end->data;
}
};


### linkedlist_reverse() method

We'll implement linkedlist_reverse() method to reverse a linked list. For doubly linked lists reverse is easy.

For doubly linked lists reverse is essentially these 2 steps: - Set list.end() as the new list.begin() - Set list.begin() as the new list.end().

Let's implement this for a singly linked list.

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode() : val(0), next(nullptr) {}
*     ListNode(int x) : val(x), next(nullptr) {}
*     ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/

class Solution {
public:
ListNode* prev = NULL;

}

return prev;
}
};


## Middle of the Linked List

### Problem Statement

Find the problem on Leetcode $$\to$$

### Approach

Use 2 pointers with different speed. Return the slow pointer.

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode() : val(0), next(nullptr) {}
*     ListNode(int x) : val(x), next(nullptr) {}
*     ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/

class Solution {
public:

}

while(fastPointer!= NULL && fastPointer->next != NULL){
slowPointer = slowPointer->next;
fastPointer = fastPointer->next->next;
}

return slowPointer;
}
};


Same function implementation but on std::forward_list<typename> container.

#include <forward_list>
#include <iostream>

using std::cout;
using std::endl;
using std::forward_list;

template <class T>
T findMiddleElement(forward_list<T> *list) {

// Using 2 pointer approach
auto slowPointer = list->begin();
auto fastPointer = list->begin();

// Update the slowPointer slowly and fastPointer quickly

while (fastPointer != list->end() && std::next(fastPointer, 1) != list->end()) {
}

return *slowPointer;
}


## Merge 2 sorted lists

Find the problem on Leetcode $$\to$$

### Problem Statement

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Input: list1 = [1,2,4], and list2 = [1,3,4]
Output: [1,1,2,3,4,4]


### Approach

We'll use the merge subroutine from the merge sort in order to merge these two lists. One problem is that the std::forward_list<typename> do not have a push_back() method. Only have a push_front() method. So we need to reverse the list before returning it. Using std::list<typename> which is a doubly linked list will give us the sorted linked list instead of the reverse sorted linked list.

### Code

#include <forward_list>
#include <iostream>

using std::cout;
using std::endl;
using std::forward_list;

template <class T>
forward_list<T> mergeTwoSortedLists(forward_list<T> *list1, forward_list<T> *list2) {
forward_list<T> mergeList; // Output linked list O(N) space.

auto list1_ptr = list1->begin();
auto list2_ptr = list2->begin();

while (list1_ptr != list1->end() && list2_ptr != list2->end()) {

if (*list1_ptr < *list2_ptr) {
mergeList.push_front(*list1_ptr);
} else if (*list1_ptr > *list2_ptr) {
mergeList.push_front(*list2_ptr);
} else {
mergeList.push_front(*list1_ptr);
}
}

if (list1_ptr == list1->end() && list2_ptr != list2->end()) {
while (list2_ptr != list2->end()) {
mergeList.push_front(*list2_ptr);
}
} else if (list1_ptr != list1->end() && list2_ptr == list2->end()) {
while (list1_ptr != list1->end()) {
mergeList.push_front(*list1_ptr);
}
}

mergeList.reverse();
return mergeList;
}


### Time and Space complexity

Time complexity is $$O(N)$$ and space complexity is $$O(1)$$ with this implementation.

### Implementing this problem in-place

#### Step wise iteration explainer

##### Iteration 5, and so on and the last

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode() : val(0), next(nullptr) {}
*     ListNode(int x) : val(x), next(nullptr) {}
*     ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/

class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {

if (list1 == NULL)
return list2;
if (list2 == NULL)
return list1;

auto* dummyNode = new ListNode();
auto* temp = dummyNode;

while (list1 && list2){
if (list1->val < list2->val){
temp->next = list1;
list1 = list1->next;
}else{
temp->next = list2;
list2 = list2->next;
}
temp = temp->next;
}

if (list1){
temp->next = list1;
}else if (list2){
temp->next = list2;
}

return dummyNode->next;
}
};


## Delete Node in a Linked List

Problem on Leetcode $$\to$$

### Example

Input: For element in [4,5,1,9], we are given the node 5. Remove it from the list.

Output: [4,1,9],

You are given the second node with value 5, the linked list should become 4 -> 1 -> 9 after calling your function.

### Approach

• Copy over the next node's value to this node. Remove the next node in $$O(1)$$ time and Space.
/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
void deleteNode(ListNode* node) {
ListNode* nextNode = node->next;
int valueAtNext = nextNode->val;

node->val = valueAtNext;
ListNode* nextToNextNode = nextNode->next;

node->next = nextToNextNode;
delete(nextNode);
}
};


## Remove Nth Node From End of List

Given the head of a linked list, remove the nth node from the end of the list and return its head

### Example

For elements $$[1, 2, 3, 4, 5]$$, remove the second node from the last. This will return $$[1, 2, 3, 5]$$. Similarly $$[1]$$ and $$n = 1$$ will return $$[]$$.

### Constraints

Nodes are given either in a forward_list<typename> or in a custom linked list which is defined below.

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode() : val(0), next(nullptr) {}
*     ListNode(int x) : val(x), next(nullptr) {}
*     ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/


• The number of nodes in the list is $$\mathcal{N}$$
• 1 <= $$\mathcal{N}$$ <= 30
• 0 <= (new ListNode())->val <= 100
• 1 <= n <= $$\mathcal{N}$$ (n is within the bounds).

### Approach

#### Implementation with two pass

• Find the size of the linked list.
• We need to delete the Kth node from the last, means we need to delete the $$(\text{SIZE} - K + 1)^{\text{th}}$$ element from the first node (considering index of linked list starts from 1).
• Now delete the $$(\text{SIZE} - K + 1)^{\text{th}}$$ node from the start with the upper solution.
struct ListNode{
int value;
ListNode *following;
};

int size = 0;
while (start){
start = start->following;
size++;
}

if (size <= 1){
// This means only one element is there and removing that
// should return nothing.
return NULL;
}

int indexToRemove = size - end + 1;   // Index starts from 1 in this case

if (indexToRemove == 1){
// Return head->following if indexToRemove is the first one.
}

ListNode* current = head->following;  // Mark at the 2nd element

int indxpos = 2;  // Starting from 2nd element

while (indxpos != indexToRemove){
prev = prev->following;
current = current->following;
indxpos+=1;
}

ListNode* following = current->following;
prev->following = following;
}


#### Implementation with one pass only

• With $$2$$ pointers we can easily know what is the $$n^{\text{th}}$$ node from the back of the list.
• Observation: If we make 2 pointers at a distance $$n$$ with each other. Then we move both one by one until the right pointer points to the end of the list $$\to$$ then the left pointer points to the $$n^{\text{th}}$$ node from the last.

#### A bit modification

We have to delete some node. Ideally if we could get a pointer to the previous node, it would be better. Ideally our pointer arrangement should look like this

Now walking backwards the starting arrangement of those pointers should be this way

To make that arrangement we need to traverse through the list like the following

#### Edge Case

There is 2 edgecases here. 1. They ask you to delete the first element [6th last node from the end of a 6 element list]. 2. They give you a one element list.

For second case you should add the following check

if (head->following == NULL) return NULL;


And for the first case let's run the above algorithm and see what happens.

So in this case the size of the linked list is 5 and $$N = 5$$. So now at gap = 5 right points to NULL;. We could add the check like this:

if (right){
ListNode *ref = left->following;
left->following = left->following->following;
}else{
// Delete the first Node, because right points to NULL
}


### C++ Code

ListNode *removeFromEndOnePass(ListNode*head, int end){

if (head->following == NULL) return NULL;

int currentGap = 0;

while (currentGap!= end){
currentGap++;
right = right->following;
}

if (right){
ListNode *ref = left->following;
left->following = left->following->following;

}else{
}

}


### Time and space complexity

• For both the solution $$O(N)$$. But 2 pass solution will take more time.
• Both are cosntant space solution.

### Problem Statement

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

### Testcase Examples

$$l_1 = [2,4,3] \:\&\: l_2 = [5,6,4]$$. Corrosponding Output $$= [7,0,8]$$

### Approach

• Do normal addition from 1st standard and add digit by digit in a new linked list.

### C++ code

#include <forward_list>
#include <iostream>

using std::cout;
using std::endl;
using std::forward_list;

forward_list<int> addTwoNumbers(forward_list<int> *number1, forward_list<int> *number2) {
forward_list<int> result;
int digit_sum;
int carryFlag = 0;

auto n1iter = number1->begin();
auto n2iter = number2->begin();

while (n1iter != number1->end() && n2iter != number2->end()) {
if (carryFlag == 0) {
digit_sum = 0;
} else {
digit_sum = 1;
}

digit_sum += (*n1iter + *n2iter);

if (digit_sum >= 10) {
carryFlag = 1;
} else {
carryFlag = 0;
}

result.push_front(digit_sum % 10);
}

// While loop broken meaning both are same or any one
// of the numbers have more digits.

if (n1iter != number1->end() && n2iter == number2->end()) {
// Means n2 got finished and n1 remains
while (n1iter != number2->end()) {
if (carryFlag == 0) {
digit_sum = (*n1iter);
} else {
digit_sum = (*n1iter) + 1;
}

if (digit_sum >= 10) {
carryFlag = 1;
} else {
carryFlag = 0;
}

result.push_front(digit_sum % 10);
}
} else if (n1iter == number1->end() && n2iter != number2->end()) {
// Means n1 got finished and n2 remains
while (n2iter != number2->end()) {
if (carryFlag == 0) {
digit_sum = (*n2iter);
} else {
digit_sum = (*n2iter) + 1;
}

if (digit_sum >= 10) {
carryFlag = 1;
} else {
carryFlag = 0;
}

result.push_front(digit_sum % 10);
}
}

if (n1iter == number1->end() && n2iter == number2->end()) {
// Both got ended, then add 1 from the carry to the result
if (carryFlag) {
result.push_front(1);
}
}

return result;
}


### C++ code for leetcode with custom definition for singly-linked list

Instead of using the stl itself C++ solution on a custom linked list.

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode() : val(0), next(nullptr) {}
*     ListNode(int x) : val(x), next(nullptr) {}
*     ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {

int digitLevelSum;
int carry = 0;

while(l1 && l2){

digitLevelSum = 0;
if (carry == 0){
digitLevelSum = l1->val + l2->val;
}else{
digitLevelSum = l1->val + l2->val + 1;
}

if (digitLevelSum >= 10){
carry = 1;
}else{
carry = 0;
}

ListNode* digitLevelEntry = new ListNode(digitLevelSum % 10);

temp->next = digitLevelEntry;
temp = digitLevelEntry;

l1 = l1->next;
l2 = l2->next;
}

if (l1 != NULL && l2 == NULL){
while(l1){
digitLevelSum = 0;

if (carry == 0){
digitLevelSum = l1->val;
}else{
digitLevelSum = l1->val + 1;
}

if (digitLevelSum >= 10){
carry = 1;
}else{
carry = 0;
}

ListNode* digitLevelEntry = new ListNode(digitLevelSum % 10);

temp->next = digitLevelEntry;
temp = digitLevelEntry;

l1 = l1->next;
}
} else if (l1 == NULL && l2 != NULL){
while(l2){
digitLevelSum = 0;

if (carry == 0){
digitLevelSum = l2->val;
}else{
digitLevelSum = l2->val + 1;
}

if (digitLevelSum >= 10){
carry = 1;
}else{
carry = 0;
}

ListNode* digitLevelEntry = new ListNode(digitLevelSum % 10);

temp->next = digitLevelEntry;
temp = digitLevelEntry;

l2 = l2->next;
}
}

if (!(l1&&l2)){
if (carry == 1){
ListNode* digitLevelEntry = new ListNode(1);
temp->next = digitLevelEntry;
}
}

}
};


## Intersection of Two Linked Lists

Find the problem on Leetcode $$\to$$

### Problem Statement

Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.

### Example

For the following problem, head1 and head2 are given, find the marked blue intersection point.

### Approach

#### Brute Force approach

• For each element in list1, check if the element is in list2 by comparing the addresses not the values because values can be same in different lists.
• This takes $$O(M*N)$$ time and no extra space.

#### Using Hash table

• As we have to compare if something is present or not we can use hash table to do so.
• If the node is present in both the list means, they must have the same value and the same address.
• First we'll create an std::unordered_map<long long int, int> dict;. The key should be long long int address of list nodes, and the value should be the value at that address.
• Now for each element in the second list check that std::unordered_map<long long int, int> dict; has that value or not. If both the value and the address of the value is present in the second list means this is the first merge point.

#### C++ Code

class Solution {
public:

std::unordered_map<long long int, int> dict;

// Iterate and Add all the entries of listA
while(listAiterator){

// Convert the address to a long long int
long long int address = reinterpret_cast<long long int>(listAiterator);

listAiterator = listAiterator->next;
}

// Now for all element see if the address is already in the map?
// If it's in the map means this is the merge point.

while(listBiterator){

// cast the address to a long long int
long long int address = reinterpret_cast<long long int>(listBiterator);

if (search != dict.end()){
break;
} else {
listBiterator = listBiterator->next;
}
}

if (listBiterator){
return listBiterator;
}

return NULL;
}
};


#### Time and Space Complexity

• As we are going through the list once so the time is $$O(M + N)$$ where $$M$$ and $$N$$ are length of the lists.
• Additional $$O(M)$$ or $$O(N)$$ space is required whatever you choose to store first.

### Linear time and Constant Space Approach

• Now check what is the problem here? Here we don't know how long after the merge point occurs. Both the lists can be of any size so we can't compare them directly and advance. But what if we resolve the difference and synchronize them with each other? Let's see what I mean:

### C++ Code for Most Optimal Approach

class Solution {
public:
int sizeA = 0;
int sizeB = 0;

// O(max(m, n))

while(Aptr || Bptr){
if (Aptr){
sizeA++;
Aptr = Aptr->next;
}
if (Bptr){
sizeB++;
Bptr = Bptr->next;
}
}

int headerDifference = sizeA - sizeB;

// Size B is higher
}
} else {
// Size A is higher
}
}

}else{
}
}

return NULL;
}
};


#### Time and Space Complexity

• The size calculation take $$O(M)$$ where $$M$$ is the size of the bigger list, and last while loop runs $$O(N)$$ where $$N$$ is the size of the smaller list. So overall $$O(M+N)$$ is the time complexity.
• No extra space required.

## Detect a cycle in linked list

### Approach

• Create 2 pointers and then move ahead,
• slow pointer will move one step up,
• fast pointer will move twos step up,
• if fast pointer reaches NULL somehow, this means there is no cycle in linked list.
• If that does not happens and some time after fast == slow, means there is a cycle in linked list. Return true.

### C++ Code

class Solution {
public:

while (fast && fast->next && fast->next->next){
slow = slow->next;
fast = fast->next->next;

if(slow == fast){
return true;
}

}

return false;
}
};


#### Time and space complexity

• $$O(N)$$ time and no extra space.

### Problem Statement

Given the head of a singly linked list, return true if it is a palindrome.

### Approach With More Space

• First we push all the value to a new stack.
• Then we pop the value and compare it to the list head. If same we move forward and if not we return false.

#### C++ Code

class Solution {
public:

vector<int> stk;

}

return false;
}

stk.pop_back();
}

return true;
}
};


### More optimized approach

• Break down the linked list into 2 parts by finding the middle.
• From the middle element reverse the linked list.
• Now again find the middle of the linked list, and then from head go ahead comparing with middle element and move forward. If you find any element which is not equal return false.

class Solution {
private:

ListNode* prev = NULL;

while(current){
ListNode *nextToCurrent = current->next;
current->next = prev;
prev = current;
current = nextToCurrent;
}

return prev;
}

while(fast and fast->next){
slow = slow->next;
fast = fast->next->next;
}

return slow;
}

int sz = 0;

while(i_ptr){
i_ptr = i_ptr->next;
sz++;
}

return sz;
}

public:

// Reverse from mid point

while(traverse->next != midpoint){
traverse = traverse->next;
}

// Now the thing is reversed.
// Now get the length of the list

if (size % 2 != 0){
// The list is not even length means there is one random element at the middle
ListNode *traveler = newMidPoint;

while(traveler->next){
return false;
}
traveler = traveler->next;
}
} else {
// The list is even length.
ListNode *traveler = newMidPoint;

while(traveler){
return false;
}
traveler = traveler->next;
}
}
return true;
}
};


## Find the starting point of cycle in linked list

Problem on Leetcode $$\to$$

### Problem Statement

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.

Do not modify the linked list.

### Constraints

• The number of the nodes in the list is in the range [$$0$$, $$10^4$$].
• $$-10^5$$ <= Node.val <= $$10^5$$
• You solve it using $$O(1)$$ (i.e. constant) memory,

// Definition for singly-linked list.
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};


### Approach with extra space

• We can hash all the nodes while traversing the list,
• If we find a node == nullptr we stop and say NO cycle present.
• Else if we find a node that has been already hashed then we say this is the entry point of the cycle.

#### Pseudocode for this apporach

ListNode* hash = HashTable();

while(node){
if (hash.contains(node)){
return node;
}
hash(node);
node = node.next;
}


#### Time and Space complexity

• Time is $$O(N)$$,
• Space is $$O(N)$$ for the hashtable.

### Approach with no extra space

• First we run the sub-routine of if_has_loop(),
• That algorithm stops (if linked list has loop) when the slow and the fast pointer points to the same node.
• If you observe closely this point will be equi-distant from the node where the cycle started as the head to the node where the cycle started.
• Now we can advance a ref. pointer to head and the slow or fast pointer by 1 until they meet.

### Video for intuition

The following is a video explaining why this apporach works?

#### C++ Code

class Solution {
public:

while((fastPointer!=nullptr) and (fastPointer->next!=nullptr)){
slowPointer = slowPointer->next;
fastPointer = fastPointer->next->next;

if (slowPointer == fastPointer){
break;
}
}

if ((fastPointer) and (fastPointer->next)){
// Means there is cycle in the list

while(slowPointer != traveller){
slowPointer = slowPointer->next;
traveller = traveller->next;
}

return traveller;
}

// Means there is no cycle in the list
return nullptr;
}
};


## Given the head of a linked list, rotate the list to the right by k places

Find the problem on Leetcode $$\to$$

### Problem Statement

Given the head of a linked list, rotate the list to the right by k places.

Test case examples

Input: head = [1,2,3,4,5], k = 2 Output: [4,5,1,2,3]

Input: head = [0,1,2], k = 4 Output: [2,0,1]

### Constraints:

1. The number of nodes in the list is in the range $$[0, 500]$$
2. $$-100$$ <= Node.val <= $$100$$
3. $$0$$ <= k <= $$2 * 10^9$$

### Approach

• First of all the thing is if the size of the linked list is $$K$$ then doing exactly K rotation is essentially doing nothing. For example
• So total of $$k \text{ mod size of the list}$$ meaningful rotations are actually happening. This is the way we can reduce the high $$2 * 10^9$$ number down to the range $$0 \to 500$$ the size of the list.
• Now armed with this knowledge, we can think of what it means to be rotating the list?
• In the above picture observe that rotating this list by 2 step is actually setting the $$\text{size} - K^{th}$$ element's next = NULL,
• and add the last 2 elements to the front of the list.
• We can approach this via the following way:
• First set the final element's next = firstNode.
• Now set the point where it supposed to be the new head by breaking off the prevNode's next = NULL.

### C++ Code

class Solution {
private:
int size = 0;

size++;
}

size++;

}

public:
ListNode* rotateRight(ListNode* head, int k) {

}

int size = p.first;
ListNode *last = p.second;

int numberOfRotation = k % size;  // Number of effective rotation

// now last points to the last node
// making it full circle

// figure out the break point?
int breakPoint = size - numberOfRotation;

int index = 1;
while(index!=breakPoint){
index++;
}

}
};


### Another Approach

• We get hold of the last node and the size of the list,
• Rotating k times to the right means rotating $$\text{size} - k$$ times to the left,
• Once we have that, rotating left is as easy as the following
• Set markers on start and end of the list,
• Set new head as the head->next,
• Set end->next as the node previously at the start of the list,
• Set new end as this node, and
• Set new end->next as nullptr
• This is how we can easily rotate the list.

### C++ Code

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode() : val(0), next(nullptr) {}
*     ListNode(int x) : val(x), next(nullptr) {}
*     ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
private:
int size = 0;
size++;
}
return size;
}
public:
ListNode* rotateRight(ListNode* head, int k) {

// k times rotate to the right means size - k  times rotate to left
int rotations = size - (k % size);

// set the end pointer
while (end->next) end = end->next;

while (rotations > 0) {
ListNode* tempEnd = end;

rotations--;
}

}
};


## Copy List with Random Pointer

Find the Problem on leetcode $$\to$$

### Problem Statement

A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null.

Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.

For example, if there are two nodes X and Y in the original list, where X.random --> Y, then for the corresponding two nodes x and y in the copied list, x.random --> y.

The linked list is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

• val: an integer representing Node.val
• random_index: the index of the node (range from 0 to n-1) that the random pointer points to, or null if it does not point to any node.

### C++ Node definition

class Node {
public:
int val;
Node* next;
Node* random;

Node(int _val) {
val = _val;
next = NULL;
random = NULL;
}
};


### Approach

• Create a new node traveller, which will be returned as the new deep copy of the linked list. For each element in the list create a new node in the deep copy of the list.
• During this time also record a unordered_map<long long int, long long int> of list nodes and corrosponding deep copy of the node's address.
• Now for each element in list and deep copy of the list, set the deep copy node's random pointer to the address of map[list.random].
class Solution {
public:

Node *copy = new Node(-6969);

Node *copyTraveller = copy;

unordered_map<long long int, long long int> map;

while(traveller){
long long int thisNodeAddress = reinterpret_cast<long long int> (traveller);
int thisNodeValue = traveller->val;

// Create a node copy and store the address here for later mapping.
Node *nextCpy = new Node(thisNodeValue);
copyTraveller->next = nextCpy;
copyTraveller = copyTraveller->next;

long long int copyNodeAddress = reinterpret_cast<long long int> (nextCpy);

traveller = traveller->next;
}

Node* traveller1 = copy->next;

while(traveller1 and traveller2){

traveller1->random = reinterpret_cast<Node*> (map[reinterpret_cast<long long int> (traveller2->random)]);

traveller1 = traveller1->next;
traveller2 = traveller2->next;
}

return copy->next;
}
};


### Time and Memory complexity

• We are traversing the list 2 times so $$O(\mathcal{N})$$ time and
• we are using a map with max of $$\mathcal{N}$$ elements so $$O(\mathcal{N})$$ memory complexity.

## Merge k Sorted Lists

### Problem Statement

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

### Example

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
[
1->4->5,
1->3->4,
2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

Input: lists = []
Output: []

Input: lists = [[]]
Output: []


### Approach

• To merge $$K$$ sorted list we'll use a subroutine merge $$2$$ sorted list.
• Using that merge2list subroutine will merge like the merge sort algorithm, and the result will be a sorted list.
• To merge 2 sorted list you should watch the explaination here.

### Code

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode() : val(0), next(nullptr) {}
*     ListNode(int x) : val(x), next(nullptr) {}
*     ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
private:

ListNode* l1;
ListNode* l2;

}

}

ListNode* dummy = new ListNode();
ListNode* temp = dummy;

while (l1 and l2) {
if (l1->val < l2->val) {
temp->next = l1;
l1 = l1->next;
} else if (l1->val >= l2->val) {
temp->next = l2;
l2 = l2->next;
}
temp = temp->next;
}

if (!l1) temp->next = l2;
if (!l2) temp->next = l1;

return dummy->next;
}

public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
// call mergeSubRoutine on 2 lists
// until mergeAll results to 1 list only
if (lists.size() == 0) return nullptr;
if (lists.size() == 1) return lists[0];

while (lists.size() > 1) {
vector<ListNode*> temp;
for (int i=0; i<lists.size(); i+=2) {

// take up 2 lists to merge
ListNode* l1 = lists[i];
ListNode* l2;

if (i+1 > lists.size() - 1) {
l2 = nullptr;
} else {
l2 = lists[i+1];
}

temp.push_back(merge2list(l1, l2));
}

// now in temp we have all the 2 merged lists
// we should update the lists as the temp
lists = temp;
}

// at the end all are merged so we've only one list, so return it
return lists[0];
}
};


## Reverse Nodes in k-Group

Find the Problem on Leetcode $$\to$$

### Problem Statement

Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is.

You may not alter the values in the list's nodes, only nodes themselves may be changed.

### Example

Input: head = [1,2,3,4,5], k = 2
Output: [2,1,4,3,5]


### Approach

• We'll find the $$k^{th}$$ node from the head of the list and then reverse it in-place, let's call it a group
• We'll then jump k places to reverse the next group, until we find the last group where there is remaining $$\geq 0 \text{ and} \leq k$$ elements. Then we stop there.

### Code

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode() : val(0), next(nullptr) {}
*     ListNode(int x) : val(x), next(nullptr) {}
*     ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
private:
ListNode* kth(ListNode* head, int k) {
while (head and k > 0) {
k--;
}

}
public:
ListNode* reverseKGroup(ListNode* head, int k) {
auto dummy = new ListNode(0, head);

auto prevEnd = dummy;

while (true) {
auto kthNode = kth(prevEnd, k);
if (not kthNode) break;
auto groupNext = kthNode->next;

// we have the head and the kth node
// so we should reverse it
auto prev = groupNext;
auto current = prevEnd->next;

while (current!=groupNext) {
auto temp = current->next;
current->next = prev;
prev = current;
current = temp;
}

auto temp = prevEnd->next;
prevEnd->next = kthNode;
prevEnd = temp;
}

return dummy->next;
}
};