# Non repeating character in stream of characters

In post here , we learned how to find first non repeating character in a string. In this case, entire set of character was available to us up front. Now, let’s see a problem where there is a stream of characters and not a string. So, the problem statement is something like this : Given a stream of characters, find first non repeating character at any given point of time. For example stream is like a,b,c,c,c,b,a,d,e,e,f,…. First non repeating character in this stream till now is d. So, we have to return first non repeating character at a given point of time.

If there is predefined set of characters and task is to figure out first non repeating character, then it is very simple. Create a hash table keyed on character and as and when character is encountered in given set, increase the count. Once all characters in set are processed, go through the set again and return the first character which occurs once in set.

However, this approach cannot work when there is continuous stream of characters. We need a different approach. First of all, keep in mind that we have find first non repeating character a given point of time. If we query at time t0 and next instance of character comes at t1 where t1> t0, we will return the character at t0. When character is seen second time, it will be discarded. But what will be first non repeating character at t1 then?

## Figure out data structures and behavior

In order to answer above question, store all the characters which are non repeating till t0 and when queried for first non repeating character, return first character in the list. Got some hint?
There is a pattern of characters coming in and leaving out and that is First come first out. Which data structure provides that? Yes, Queues. We have finalized one thing : To get non repeating character at any time we need to implement queue and store each character which is seen only once in that queue.

Second part is to remove a character when it occurs again. As characters seen only once till given point of time are stored in queue, we need to remove node from queue.  This node can be at anywhere in queue. What is the best structure where to implement queue when we have to delete node at anywhere, from start, end or middle ? Doubly linked list.  Till now we have figured out how to delete a node or character entry from queue when it occurs second time and how to get first non repeating character.

However, how to find the exact node to be deleted in queue implemented using doubly linked list. Either we traverse DLL each time with O(n) complexity, or we can store a mapping. Mapping will be between character and node pointer in DLL. Given a node pointer in DLL, how to delete it can be read here :Delete a node from doubly linked list

There is a small catch here : What if the character is seen third time ? We go to the hash <character, node> and get the node. Then try to free the node again which is already freed when it occurred second time. In this case, segmentation fault for sure! 🙂

One solution is to remove node from the hash. But then there is no way if the character never appeared or appeared twice.
To check if character is seen two or more times, use another hash with character as key and boolean as value. Set hash <character> to true when character is seen second time. So, first check in this hash, if the character entry in map is true, do not do any processing.

Great! We have got data structures. Now let’s summarize algorithm to find first non repeating character in stream of characters
```1. Take the input character.
2. Check in 'visited' hash if this character is seen twice already.
3. If yes, don't do anything, process next character.

4. If it not seen twice yet, then we need check if it is seen first time. If seen first time, DDL node entry corresponding to that character will be null.
5. Add node in DLL and update the hash table with the node value.

6. If character is already seen once, we will have a node entry in hash table. Remove the node from queue and marked 'visited' entry as true```
Let’s work out an example: Stream of characters is : a,t,r,e,r,a,p,p,p,a,u,i,b,t,………….Continues. At first all our containers are false and NULL, queue is empty.

Initial state

Character ‘a’ comes : Looking at visited array,we see that it is definitely not seen more than twice, else the place would have been marked true. Also looking at node map array we can see that this character is still not in queue, it means we have seen it first time. So we add this to queue and store pointer in node map array.
Data structure condition :
Now comes ‘t’, same above conditions are true, hence ‘t’ is also added to queue. Similarly for r and e too.

When first instance of a character is seen

Twist comes when ‘r’ is seen again. This time we have a node pointer stored in node map array corresponding to ‘r’, but visited flag is false. This means we have seen ‘r’ second time. We till remove node ‘r’ from queue and mark visited[‘r’] as true, hence forth character will not considered as first non repeated character. So our data structures at this point look like this:
When second instance of character is seen

After this if query for first non repeated character, output will be ‘a’.
We process next character ‘a’. Again same fate as above ‘r’. We will remove node from the queue and marked visited[‘a’] as true.
After this if query for first non repeated character, output will be ‘t’.
This will continue is similar fashion. Please comment if further explanation is required on example.

## Code to find first non repeating character

Complexity of to find first non repeating character will be O(1) to find first non repeating character at a given point of time. We would use NO_OF_CHARACTERS extra space.

## Palindrome linked list : 3 Methods

```   1->2->3->3->2->1->NULL is palindrome linked list where as,
1->3->2->4->2->1->NULL is not a palindrome linked list
```

By definition of palindrome, a linked list is palindrome if it reads forward and backwards same.

To check if string is palindrome, standard way is to keep to pointers, one moving from left to right and other from right to left and at each point we check if  character at this place match. If at any place they don’t match, we will say string is not palindrome and return. Once two pointers cross each other, we say string is palindrome. Now can we apply that algorithm on linked list? No, because we cannot move backward that is from right to left in case of singly linked list. So what is the way?

## Methods to find palindrome linked list

Using stack to find if linked list is palindrome
One way is to put list on stack. Now pop each element from the stack and move forward in original linked list. If all nodes on stack and linked list match, linked list is palindrome.

Palindrome check by reversing linked list
Another way is to reverse the entire linked list into a new linked list and scan both linked list simultaneously in forward direction. If they differ at any point of time, return false. However, this takes O(N) extra space.

We can reduce space required to half by reversing only half of list and compare that will other half. Even we can do away with n/2 extra space by reversing half of list in place and find if list is palindrome and then again reverse half part of linked list.

```1. Get to the middle of linked list
2. Reverse the second half of list
3. Compare first half and second half
3.a If both are identical, list is palindrome
3.b If both are not identical, list are not palindrome```

In above algorithm, there is one catch. What if number of nodes in linked list is odd, then middle node should not be considered as part of any sublist. How can we find if there are odd number of nodes? Well, when we are traversing list to find middle node, if fast pointer is not null, then there are odd number of node.

```#include<stdio.h>
#include<stdlib.h>

#define true 1
#define false 0

typedef struct Node {
int data;
struct Node * next;
} Node;

Node * createNode(int val){
Node * newNode = (Node *)malloc(sizeof(Node));
if(newNode){
newNode->data = val;
newNode->next = NULL;
}
return newNode;
}

/* This function inserts node at the head of linked list */
Node * newNode  = createNode(data);
}

}
printf("Null");
}

// We are returning next node as it will be required in calling function
Node * reverseList(Node *node){

Node *current = node;
Node *prev = NULL;
Node *next = node;

while(current){
next = current->next;
current->next = prev;
prev = current;
current = next;
}
return prev;
}

while(L1 && L2){
if(L1->data != L2->data) return false;
L1 = L1->next;
L2 = L2->next;
}
if(!(L1 && L2))
return true;

return false;
}

Node *prev = NULL;
Node *midNode = NULL;
/* We are finding the middle node.*/
while(fast && fast->next){
fast = fast->next->next;
/* We are saving previous node because that
will be end of fist list
in case of even number of nodes */
prev = current;
current = current->next;
}

/*Check if there are odd number of nodes,
if fast pointer is null, then
there are even number of nodes, else it's odd number */
if(fast){
midNode = current;
current = current->next;
}

//Let's reverse second half of list

prev->next  = NULL;

//Reverse back second half

//If there are odd number of nodes, midNode should not be null
if(midNode){
prev->next = midNode;
midNode->next = current;
}
else
prev->next = current;

return isPalindrome;
}

int main(void) {

printf("\nOriginal list :");
printf("\nIs list palindrome : %s",
return 0;
}
```

## Recursive method to find if list is palindrome linked list

Recursive method is quite interesting, in this we have two pointers, one moving forward and other moving backward. As we have seen in couple of problems here and here, how can we move a pointer backward in linked list using recursion. How and when to move forward pointer? We need to compare first node of list with last of list; 2nd with n-1th and so on till backward and forward pointers cross each other.

Forward pointer will be at head till the time we reach at the end of list. Once we are at last node, we can compare first and last node and recursion starts unwinding. Recursive call which had previous to last node should be comparing 2nd node and so on, hence as recursion starts unwinding, move forward pointer ahead. And since updated value of that pointer is needed in calling function, use and pass reference to it. Advantage of this method is that we don’t need to modify linked list at any time.

```1. Start with two pointers forward and backward
2. Till there are nodes in list
2.a move backward pointer ahead and keep forward constant
3. Once reached at end
3.a compare forward with backward pointer, if not equal, return false
3.b else move forward pointer ahead```
```#include<stdio.h>
#include<stdlib.h>

#define true 1
#define false 0

typedef struct Node {
int data;
struct Node * next;
} Node;

Node * createNode(int val){
Node * temp = (Node *)malloc(sizeof(Node));
if(temp){
temp->data = val;
temp->next = NULL;
}
return temp;
}

/* This function inserts node at the head of linked list */
Node * newNode  = createNode(data);
}

}
printf("Null");
}

int isPalindromeUtil(Node **forward, Node *backward){
//There are no nodes is lists
if(!backward) return true;

/*we are recursing moving backward pointer ahead.
Backward pointer will start moving backward once
we hit above terminal condition of recursion */
int isPalindrome = isPalindromeUtil(forward, backward->next);

if(!isPalindrome) return isPalindrome;
/*At this point forward is n nodes ahead from start
and backward n nodes away from end n varies from 0 to n
Compare forward and backward
*/
if((*forward)->data != backward->data){
return false;
}
/*Move ahead forward pointer, backward will move back
automatically due to recursion */
*forward = (*forward)->next;

return isPalindrome;
}

/* we are starting with forward pointer and backward at head.
Notice that we passing reference to forward and just pointer for
backward pointer */
}

int main(void) {

printf("\nOriginal list :");
printf("\nIs list palindrome : %s",
return 0;
}
```

Notice that we defined a function isPalindromeRecursiveMethod() and then a Util function. This is very good practice because your main method need not worry about how internals of recursive function are implemented, it only passes head pointer and gets the dissuader output. This is typical case of abstraction of information.
Execution of above program:

Time complexity of palindrome linked list check algorithm using approach 2 is O(N) and space complexity is O(1). Method 3, that is recursive method has time complexity of O(n) and implicit space complexity of O(n).

# Delete node from linked list

Given a singly linked list and a value, delete node from linked list.

To delete node from a linked list, first find node to be deleted. Scan through linked list and compare given value with each node.  If value matches, it’s node to be deleted.  Let us call it current node. To delete current node, make next pointer of previous node to point to next node of current node. However, there is not any access to previous node of linked list once pointer moves forward.

So what shall we do? Idea is to keep track of previous node while traversing the linked list forward.

With this approach, take care of three cases

```1. When node to be deleted is head node.
2. When node to be deleted is any of middle nodes.
3. When node to be deleted is last node of linked list.```

In first case, since very first node is being deleted, head pointer of linked list should be updated. For second and third case, just change pointers as explained above. (Next of previous node points to next of current node).

## Delete node from linked list implementation

```
#include<stdlib.h>
#include<stdio.h>

typedef struct Node {
int data;
struct Node * next;
} Node;

//If list is null

//If the node to be deleted is head node
free(temp);
}
else{
//Scan till node, also save the previous pointer
while(current && current->data != value){
prev = current;
current = current->next;
}
//If we found the node, connect prev and next of node
if(current){
prev->next = current->next;
free(current);
}
}
return;
}

/* Create a node of linked list */
Node * createNode(int val){
Node * newNode = (Node *)malloc(sizeof(Node));
if(newNode){
newNode->data = val;
newNode->next = NULL;
}
return newNode;
}

/* This function inserts node at the head of linked list */
Node *newNode  = createNode(data);
}

printf("\n");
}
printf("Null");
}

int main(){
Node *L1 = NULL;

push(&L1,3);
push(&L1,4);
push(&L1,6);
push(&L1,7);
push(&L1,8);
push(&L1,1);
push(&L1,10);

printList(L1);

deleteNode(&L1, 6);

printList(L1);
return 0;
}
```

What if interviewer asks you not to use previous pointer. There is a very well known method for that too. Idea is to traverse till node to be deleted. Then copy value of next  node onto current node. Once done, change next pointer of current node to point to next of next node.

This method does not work if node to be deleted is last node of linked list. In that case even if we avoid accessing null node after last node, we may not be able touch previous node’s next pointer, which will point to a freed node because we delete last node. Good point to make in interview.

For more details on this method please refer : delete a node given a reference to to that node

```void deleteNode(Node **head, int value){
free(temp);
}
else{
Node * temp;
while(current && current->data != value){
current = current->next;
}
if(current && current->next){
current->data = current->next->data;
temp = current->next;
current->next = current->next->next;
free(temp);
}
}
return;
}
```

Complexity of algorithms to delete node of a linked list is O(N), where N is number of nodes in linked list.

There is another problem closely related  with deleting a node: Delete linked list.
To delete linked list, all nodes of linked list must be deleted. Also, before deleting node, next node should have been deleted. That means before deleting head, all nodes of linked must have been already deleted. To do so, we have to start delete operation from end of linked list. Delete tail node, then node prior to it, then node prior to it, and so on, moving backward. One way to traverse linked list in reverse order is to use recursion.

```#include<stdlib.h>
#include<stdio.h>

typedef struct Node {
int data;
struct Node * next;
} Node;

//base case, if this last node

return NULL;
}
//If list is null

return;
}

/* Create a node of linked list */
Node * createNode(int val){
Node * temp = (Node *)malloc(sizeof(Node));
if(temp){
temp->data = val;
temp->next = NULL;
}
return temp;
}

/* This function inserts node at the head of linked list */
Node *newNode  = createNode(data);
}

printf("\n");
}
printf("Null");
}

int main(){
Node *L1 = NULL;

push(&L1,3);
push(&L1,4);
push(&L1,6);
push(&L1,7);
push(&L1,8);
push(&L1,1);
push(&L1,10);

printList(L1);

printList(L1);
return 0;
}

```

# Merge point of two linked lists

Given two linked lists, we need to find out that if two linked list merge, if yes, find merge point of two linked lists.For example:
Answer for above input should be yes and node returned should be 6

## Methods to find merge point of two linked lists

First question to be answered is whether or not two linked lists merge?
From above diagram, we can see that when two lists merge, after merge point, all nodes are same. So, that part of two linked list is common for both the lists. If two linked list merge at any given node including last node, the last node should be same. If last node of two linked lists are different, we can safely say that two linked list do not merge.

How to find merge point is second problem? There are couple of ways to find that out.
1. Brute force solution
Use two stacks and follow algorithm below:

```1. Put all nodes of linked list 1 on to stack.
2. Put all nodes of linked list 2 on another stack.
3. Pop nodes from two stack simultaneously.
4. When nodes popped are different, node popped prior to them is merge point.```

As we can see this takes O(m+n) space. Also linked list are traversed twice.

Second variant can be to use a hash.

```1. Scan all nodes of first linked list
1.a Store nodes into hash Map<Node,Boolean>
2. Now scan second linked list
2.a Check if current node is present in hash.
2.b First node which is present will be merge point.
```

This requires extra O(n) space and traversals of both lists.

Third variant of brute force method is to change linked list node itself. Each node contains a flag ‘visited’.

```1. Traverse linked list one and mark nodes as visited.
2. Traverse second list.
2.a  First node with visited flag as true is merge point```

This method does not require extra space however, changes original linked list.

2. Using lengths of merged linked lists
We can leverage the fact that linked list after merge point are same. Consider merge point as end of individual lists.If length of two linked lists is different, problem reduces to the problem where we need to reach at the end of two list at the same time. There is a simple solution to that.
We need to give longer linked list head start so that we reaches end at same time when shorter one reaches, when they are traversed simultaneously. Calculate the difference between length of two linked list and move the longer linked list traversing pointer ahead by difference. Then traverse both linked list together, when they meet that will be the merge point.

## Find merge point of two linked lists : implementation

```#include<stdlib.h>
#include<stdio.h>

typedef struct node{
int data;
struct node *next;
} Node;

int findMergePoint(Node *L1, Node *L2){

Node *current1 = L1;
Node *current2 = L2;

//If any one list is null, return false
if(!current1 || !current2 ) return -1;

//Count number of nodes in list 1;
while(current1->next){
current1 = current1->next;
}

// Count number of nodes in list 2
while(current2->next){
current2 = current2->next;
}

/*If last nodes of both linked list are not same,
if(current1 != current2)
return -1;

//Calculate the difference in lengths of linked list.

//Move the longer linked list by diff number of nodes
Node * temp = L1;
L1 = L2;
L2 = temp;
}

current1 = L1;
current2 = L2;

while(diff && current1){
diff--;
current1 =  current1->next;
}

// Now move both linked list till they meet at merge point
while(current1 != current2){
current1 =  current1->next;
current2 =  current2->next;
}
return current1->data;
}

/* Create a node of linked list */
Node * createNode(int val){
Node * temp = (Node *)malloc(sizeof(Node));
if(temp){
temp->data = val;
temp->next = NULL;
}
return temp;
}

/* This function inserts node at the head of linked list */
Node *newNode  = createNode(data);
}

printf("\n");
}
printf("Null");
}

int main(){
Node * L1 = NULL;
Node * L2 = NULL;
push(&L1,3);
push(&L1,4);
push(&L1,6);
Node * temp1 = L1;
push(&L1,7);
push(&L1,8);
push(&L1,9);
printList(L1);
printf("\n");

push(&L2,5);
Node *temp2 = L2;

push(&L2,7);
push(&L2,8);
push(&L2,2);
push(&L2,1);
push(&L2,10);

temp2->next = temp1;

printList(L2);
int result1 = findMergePoint(L1, L2);

if(result1 != -1){
printf("\n Merge Point : %d", result1);
}
else{
printf("\n Lists don't merge");
}

return 0;
}
```

Complexity of code to find merge point of two linked lists will be O(N).

# Implement Queue using linked list

In last Queue data structure , concept of queues and basic operations to be performed on it is explained. There we discussed queue implementation using array. Limitation in array based implementation is that allocation of array needs to be done before hand which restricts number of elements those can be accommodated. Other issue was to correctly gauge if queue is empty or full.  An extra counter is required for that. Today we will discuss how to implement queue using linked list. Advantage of linked list based approach is there is no pre-allocation of  size of queue. So queue is never full.

Check if queue is empty
Check head pointer of linked list, if head is NULL, queue is empty; if not, some elements are present in it.

Insertion in queue (enqueue)
Insertion into queue is done at the end or rear. Using singly linked list, traversal of entire list is required in order to add new node at end. This operation would be costly as O(N) and that is not desirable.Can we think of something else?

We can store tail pointer which points to last node of list. Or store last node pointer reference which points to next node of last node.  Initially, lastPtrPtr is set to head pointer which in turn is NULL to start with. To add node to list, directly go  to reference last pointer reference and add new node there. Update the last pointer reference. Implementation is shown below.

Deletion from queue (dequeue)
Deletion in queue is done at start. Remove the head node and then change head reference to point to next of head node. Done.

```
#include<stdlib.h>
#include<stdio.h>

typedef struct node{
int data;
struct node *next;
} Node;

Node * createNode(int val){
Node * newNode = (Node *)malloc(sizeof(Node));
if(newNode){
newNode->data = val;
newNode->next = NULL;
}
return newNode;
}

void enqueue(Node **lastPtrRef, Node *node){
//Just add node at the end.
(*lastPtrRef) = node;
}

printf("\n Queue is empty");
return NULL;
}

return returnNode;

}
}

printf("NULL");
printf("\n");
}

/* Driver program to run above code */
int main(){
Node * L1 = NULL;
Node **lastPtrRef = &L1;

enqueue(lastPtrRef, createNode(3));
lastPtrRef = &((*lastPtrRef)->next);

enqueue(lastPtrRef, createNode(2));
lastPtrRef = &((*lastPtrRef)->next);

enqueue(lastPtrRef, createNode(1));
lastPtrRef = &((*lastPtrRef)->next);

printList(L1);

dequeue(&L1);
printList(L1);
return 0;
}
```

Array based implementation is good when we are sure that queue or stack will not increase continuously and would not cross maximum size at any given point of time. Also, array based implementation has all operations in constant time and memory usage is also low as compared to linked list base implementations. However, if queue/stack can increase beyond allocate size, dynamically increasing array size is quite an expensive operation.

# Detect loop in linked list

Given a singly linked list, which may or may not contain a loop in it,detect loop in linked list and it yes, start of the loop should be returned. For example, in following linked list, function should return yes for detecting if there is loop in linked list and N3 as start of that loop.

## Methods to detect loop in linked list

Using visited flag
In singly linked list, we can traverse only in one direction and end of the list is detected when NULL pointer is encountered. What if linked list has a loop in it? Then we would never reach end of the list and circle around in the loop. When we circle around in a linked list, node which was visited earlier will be visited again. How can we remember that we have already visited node? Yes, we can mark node as visited when we visit it. At every node, before traversing further, check if visited flag is true, if yes, then linked list has a loop.

There is a drawback of this method because we need to change internals of node representation of linked list in order to add visited flag. This also leads to extra space usage in tune of O(n). However algorithm and implementation is very simple.

Using hash table
In above method, modification in nodes of linked list is done to store visited flag. To avoid that, we can maintain a hash table. Whenever a node is visited, check if node is already present in hash, if yes, then there is a loop. If linked list is completely traversed without any collision in hash, then there is no loop. Usual question asked by interviewers here is that what should be key of hash? If answer is the data in the node, next question follows is will that work for a linked list with duplicate numbers. So correct answer for above question is that node’s address should be the key and not the value. There is another data structure which provided by high level languages called as set. In this case, set is best because of it’s property that it does not allow to add duplicate elements in it. If insertion in set fails, we know that we have already added that node and hence there is a loop and the node at which first collision happens is start of loop.
Good approach, however, it requires O(n) extra space.

Using Flyod’s algorithm. (also known as Hare and Tortoise algorithm)
Basic principle of this algorithm is that if two pointers are moved at different speed to traverse a linked list, these two pointers will surely meet at a node which in the loop, if there is a loop in list.
Take two pointers, first which moves one node at a time, let it be slow; other which moves two nodes at a time, call it fast. If slow meets fast at any point of time, then there is a loop in linked list.
Traversal of two pointers in above list would be

```Slow : 2 , Fast : 3
Slow : 3 , Fast : 5
Slow : 4 , Fast : 3
Slow : 5 , Fast : 5
```

First problem is solved. If before reaching NULL, if slow meets fast, then there is a loop in list.

Why fast pointer moves only two nodes ahead and not three or any other number? This is because traversing more than two nodes at a times gives a window where slow and fast don’t meet in iteration and we might have to iterate more times. By having the fast pointer incremented by two  we guarantee that we’ll be maximizing your efficiency in the case of worst case scenario.

Second problem that is to find starting node of loop, requires some thinking.What would be the condition when slow meets fast? Can we have the length of the loop? Yes. Move the slow pointer till it again meets faster pointer and keep count of number of nodes. Let number of nodes in loop be K

Now the problem reduces to finding Kth node from the end because if there are K nodes in loop, start node of loop would be Kth node from the end of the list. Move one pointer K nodes ahead of head and keep other at head. Move both of them simultaneously. When they meet, that node is starting point of the loop.

## Algorithm to detect loop in linked list

Cycle detection

```1. Take two pointers, slow and fast and initialize to head
2. Move them at different speed,slow one step and fast two steps at a   time
3. If slow and fast point meet before slow reaches NULL, there is a loop
4. Else return false```

Starting node detection

```1. Find length of loop in linked list (K) using the meeting point of fast and slow pointer found in above algorithm.
2. Once K is known, find Kth node from end in list and that will be start of loop
```

To read more , refer find nth node in linked list from end

```#include<stdlib.h>
#include<stdio.h>

typedef struct node{
int data;
struct node *next;
} Node;

Node *ptr1;
Node *ptr2;
int k = 1, loopFound = 0, i;

while(fast){
/*Moving fast pointer two steps at a time */
fast = fast->next;
if(fast)
fast = fast->next;

slow = slow->next;
if(slow == fast){
loopFound = 1;
break;
}
}

if(loopFound){
/* We have detected a loop */
/*Let's count the number of nodes in this loop node */
ptr1  = fast;
while(ptr1 && ptr1->next != slow){
ptr1 = ptr1->next;
k++;
}

/* Now move the other pointer by K nodes */
for(i=0; i<k; i++){
ptr2 = ptr2->next;
}

/* Now if we move ptr1 and ptr2 with same speed
they will meet at start of loop */
while(ptr1 != ptr2){
ptr1 = ptr1->next;
ptr2 = ptr2->next;
}
return ptr1;
}
return NULL;
}

}
else{
Node * temp = (Node *)malloc(sizeof(Node));
if(temp){
temp->data = value;
}
}
}

/* Driver program to run above code */
int main(){
Node * L1 = NULL;
/* creating list */
push(&L1,3);
Node *lastNode = L1;
push(&L1,4);
push(&L1,6);
Node *loopNode = L1;
push(&L1,7);
push(&L1,8);
push(&L1,9);
push(&L1,7);
lastNode->next = loopNode;

loopNode = findLoop(L1);
printf("Loop in list : %s", loopNode ? "true" :"false");
printf("\nStart node : %d", loopNode ? loopNode->data : -1);
return 0;
}
```

Detect loop in linked list : Test cases

Complexity of above algorithm to detect loop in linked list will be O(N).
Space complexity is O(1) when the memory required for an algorithm is independent of its input size. Here, only 2 pointers (fast and slow) are used, which is constant. Hence the space complexity is O(1).

# Merge two sorted linked lists

Given two sorted linked list, we need to merge two sorted linked lists into one without creating any additional node i.e in O(1) space complexity. Please read basics of linked lists and insert node in sorted linked list before attempting this problem.

Coming back to merge two sorted linked list, figure shows two sorted linked lists are merged into one linked list.

## Merge two sorted linked lists : Algorithm

First, figure out which node will be the head of the resulting list. It can be easily found by comparing head nodes of both lists, whichever is smaller is the head of resultant list. Now, there are n-1 nodes in one list (from list from which head node was taken) and m nodes in another. Task is now reduced to merge these two remaining linked lists. Once we merge these two lists, next of head node will point to head of resultant linked list.

Second, at each node figure out which list to advance. Store the smaller node and then point its next to the resultant linked list which is returned by merge two linked list after removing the smaller node.
It can be implemented using recursion, same processing (merging) has to be done on n-1 and m nodes again. Base case for recursion will be when one of the linked list has been completely traversed and reached till NULL. Then we just have to attach all remaining nodes in other linked list in resultant linked list. For example if there are two lists as follows

```1->2->5->6-NULL and 3->4->7->NULL
```

In this case while comparing 1 and 3, head node will be 1 So result = Node 1 This will be head of resultant list after merge linked lists. We are left with following linked lists to be merged.

```2->5->6->NULL and 3->4->7->NULL
```

Now, again 2 and 3 are compared and result will be 3. Now linked lists to be merged are

```5->6->NULL and 3->4->7>NULL
```

At this point 3 and 5 are compared and 3 is stored as result.

`5->6-> NULL and 4->7->NULL`

With same manner when NULL node is encountered,recursion start unwinding and at every function return result which we stored will be returned and the next of previous invocation’s result node.
In the code we are storing a pointer result (node which is smaller when heads are compared), and next of that result node will be returned value of next invocation of merge function.

## Merge two sorted linked lists : Implementation

```
#include<stdlib.h>
#include<stdio.h>

typedef struct node{
int data;
struct node *next;
} Node;

Node * mergeSort(Node *a, Node *b){
Node *result = NULL;
if(!a)
return b;
else if(!b)
return a;

/* For the first node, we would set the result to either a or b */
if(a->data <= b->data){
result = a;
/* Result's next will point to smaller one in lists
starting at a->next  and b */
result->next = mergeSort(a->next,b);
}
else {
result = b;
/*Result's next will point to smaller one in lists
starting at a and b->next */
result->next = mergeSort(a,b->next);
}
return result;
}

Node * createNode(int val){
Node * newNode = (Node *)malloc(sizeof(Node));
if(newNode){
newNode->data = val;
newNode->next = NULL;
}
return newNode;
}

/* This function inserts node at the head of linked list */
Node * newNode  = createNode(data);
}

}

printf("NULL");
printf("\n");
}

/* Driver program to run above code */
int main(){
Node * L1 = NULL;
Node * L2 = NULL;
Node * result = NULL;

/* creating list 1 */
push(&L1,7);
push(&L1,6);
push(&L1,4);
push(&L1,3);
/* creating list 2 */
push(&L2,10);
push(&L2,8);
push(&L2,1);

L1 = mergeSort(L1,L2);
printList(L1);

return 0;
}
```

Explanation merge two sorted linked list implementation is shown in figure.

Above code is used when we recursively try to flatten a linked list as shown in figure below

```void printFlatList(Node *head){
}
printf("Null");
}

Node * mergeSort(Node *a, Node *b){
Node *result = NULL;
if(!a)
return b;
else if(!b)
return a;

/* For the first node, we would set the result to either a or b */
if(a->data <= b->data){
result = a;
/* Result's next will point to smaller one in lists
starting at a->next  and b */
result->down = mergeSort(a->down,b);
}
else {
result = b;
/*Result's next will point to smaller one in lists
starting at a and b->next */
result->down = mergeSort(a,b->down);
}
return result;
}

if(!root || !root->next) return root;
}
```

Merge two sorted linked list : Test cases

```1. Two equal lengths linked list
L1  = 3->6->7->9->NULL
L2 = 1->2->5->8->NULL

2. One list have elements smaller than head of other
L1 = 1->2->3->4->NULL
L2 = 5->6->7->8->NULL

3.One list as NULL
L1 = NULL
L2  = 5->6->7->8->NULL

4. Both lists are NULL
L1 = NULL
L2 = NULL

5. Scale testing
L1 with a million nodes
L2 with million nodes

6. Test case 2 with millions nodes, to see if stack overflows.

7. Linked lists with duplicate elements
L1 = 3->3->4->6->NULL
L2 = 1->1->2->6->8->NULL
```

Complexity of merge two sorted linked list in one is O(M+N), where M and N are lengths of two linked lists. Recursive implementation of algorithm has inherent space complexity of O(max(M,N)). In production, recursive implementation with space complexity which is dependent on input size is avoided. Iterative solution are better in that case.

Iterative solution to merge two sorted linked lists

```#include <stdio.h>
#include <stdlib.h>

typedef struct node{
int data;
struct node *next;
} Node;

Node * createNode(int val){
Node * newNode = (Node *)malloc(sizeof(Node));
if(newNode){
newNode->data = val;
newNode->next = NULL;
}
return newNode;
}

/* This function inserts node at the head of linked list */
Node * newNode  = createNode(data);
}

}

printf("NULL");
printf("\n");
}

Node * MergeLists(Node *list1, Node *list2) {
if (!list1) return list2;
if (!list2) return list1;

if (list1->data < list2->data) {
} else {
list2 = list1;
}
while(list1->next && list2) {
if (list1->next->data > list2->data) {
Node *tmp = list1->next;
list1->next = list2;
list2 = tmp;
}
list1 = list1->next;
}
if (!list1->next) list1->next = list2;
}

int main(){
Node * L1 = NULL;
Node * L2 = NULL;

/* creating list 1 */
push(&L1,7);
push(&L1,6);
push(&L1,4);
push(&L1,3);
/* creating list 2 */
push(&L2,10);
push(&L2,8);
push(&L2,1);

L1 = MergeLists(L1,L2);
printList(L1);

return 0;
}
```

This is a typical example of advancing pointers and keeping track of next pointers while traversing linked lists. In this implementation, List 1 (list1) always point to smaller node at after each comparison.
Since it is already know that we have taken one node from List 1, we take next node of List 1 and current node from List 2. Compare them and if next node of List 1 (list->next) is greater than other node (list2), link current node of list 1 with current node of List 2 (list->next = list2). After this step, swap List 1 and List 2 pointer.

Please share your thoughts on implementations or explanation if something can be improved or if something is wrong and sharing is caring! 🙂

Given two linked lists, each node contains one digit of numbers, add two numbers represented by linked lists. Result should be third linked list. It should be noted that head nodes of linked lists contain most significant digit of numbers. For example, two numbers 12345 and 56789 are represented in form of linked list as follows:

```First list : 1->2->3->4->5->NULL
Second list : 5->6->7->8->9->NULL
```

Result of add two numbers represented by linked lists above should be:

```6->9->1->3->4->NULL
```

Another case:

```First list : 5->8->7->NULL
Second list: 6->5->3->NULL
Resultant list : 1->2->4->0->NULL (notice :new head node is created)
```

One way to solve this is to reverse two given linked list, add them up and finally reverse resultant list which will represent result of add two numbers represented by linked lists.

There is another way where linked list are not reversed. Addition of two numbers starts from least significant digit, start from last node of both lists and add them up, create new node to store result. Take care of the carry if sum of two numbers in nodes is more than 10. Put this node as next of node which is generated when second least significant nodes are added and continue till heads of two lists are added.

Here, there is something which is interesting. Once last nodes are added, we are left with task to add two linked list, each one node less. That mean once last nodes of two lists are added, original problem reduces to subproblem which can be solved in exactly same manner. Rings some bell? This is very good case for recursion.

However, we need to take into account the difference in number of digits in two number which will result in different number of nodes in linked list.So before starting recursion, calculate length of two lists and move longer list pointer to appropriate place so  last nodes of both lists are visited at same time.

Second, take care of carry which is generated by adding two numbers. If two numbers add up more than 10, we need to forward carry to next nodes and add carry to them. If most significant digit addition results in carry, create an extra node to store carry.

Third, see that resulting nodes are linked correctly and final list in correct order.

There is no algorithms as such, this problem involves working with recursion on linked lists and pointer handling. So let’s see implementation.

```#include<stdlib.h>
#include<stdio.h>

typedef struct node{
int data;
struct node *next;
} Node;

int length( Node * head ){
int len = 0;
while(current){
len++;
current = current->next;
}
return len;
}

Node * createNode(int value){

Node * newNode = (Node *)malloc(sizeof(Node));
newNode->data = value;
newNode->next = NULL;

return newNode;

}

Node *newNode = createNode (value);
}
else{
}
}
/* This function is actually helper function which
does all house keeping like calculating lengths of lists,
calling recursive implementation, creating extra
node for carry in MSD,and adding any remaining nodes
left in longer list. */

/* result is pointer to pointer to the head of resulting node */
void addTwoNumbers(Node *L1, Node *L2, int *carry, Node  **result){
int len1 = length( L1 );
int len2 = length( L2 );
int diff = 0;

if(len1 < len2){
Node * current = L1;
L1 = L2;
L2 = current;
}
diff = abs(len1-len2);
Node * current = L1;

while(diff--)
current = current->next;

/* Call the recursive implementation */

diff = abs(len1-len2);

/* Add remaining nodes in longer list */

if(*carry){
push(result, *carry);
}
return;
}

void addListRecursively(Node *L1, Node *L2, int *carry, Node **result){

int sum;
if(!L1)
return;

/*We have reached the last node of both lists, add them */
sum = L1->data + L2->data + (*carry);

int value = sum%10;
*carry = sum/10;
push(result, value);

return;
}

void addRemainingDigits(Node *L1, int *carry, Node **result, int diff){
int sum = 0;

if(!L1 || !diff)
return;

sum = L1->data + (*carry);
int value = sum%10;
*carry = sum/10;

push(result, value);

return;
}

void printList( Node * head ){
while(current){
printf("%d ->", current->data);
current = current->next;
}
printf("NULL");
}
/* Driver program to run above code */
int main(){
Node * L1 = NULL;
Node * L2 = NULL;
Node * result = NULL;
int carry = 0 ;
/* creating list 1 */
push(&L1,3);
push(&L1,4);
push(&L1,6);
push(&L1,7);
/* creating list 2 */
push(&L2,8);
push(&L2,9);
push(&L2,7);

printList(L1);
printf("\n");
printList(L2);

printf("\n");
printList(result);
return 0;
}
```

```1. Two lists are of same length
L1 = 1->2->3->NULL
L2 = 4->5->6->NULL

2. Two lists of different length
L1 = 1->2->3->4->NULL
L2 = 4->5->6->NULL

3. One list being NULL
L1= NULL
L2 = 4->5->6->NULL

4. Both lists are NULL
L1 = NULL
L2 = NULL

5. Carry generated
L1 = 9->4->5->NULL
L2 = 2->4->6->NULL
```

Since we need to traverse the no of nodes in longer list, complexity of algorithm would be O(N), where N is no of nodes in longer list. Also we need N extra nodes to store the result. Hence space complexity of algorithm to add two numbers represented by linked list is O(N).

# Linked list algorithms and operations

In this post, we will discuss linked list algorithms for basic operations on linked list like insert node, delete node and traverse a linked list.

Linked list is a collection of nodes, these nodes being connected to each other using pointer usually referred to as next pointer which stores pointer to immediate next node in linked list. Last node stores NULL as next pointer and that signifies end of list. Typical declaration of node  is as follows

```typedef struct Node {
void * data;
struct Node * next;
} Node;
```

Any node in linked list contains data which can be anything like integer, character, or string or any other structure itself. It also contains a pointer of same type as node type which points to node next to this node as explained above.Typical example of linked list is shown in figure below:

Process of adding a node into a linked list is called as insertion. There are three places where a node can be inserted into linked list.

```1. At start or head of linked list
2. At end or tail of linked list

Before going into details of placing a node, we first need to create a node. To create any node, three steps are to be performed:

```1. Allocated node
2. Set data of allocated node to value provided.
3. Set next pointer to NULL (we will modify it later when we place node in list).
```

Allocation of node

```Node * create_node(int val){
Node * newNode = (Node *)malloc(sizeof(Node));
if(newNode){
newNode->data = value;
newNode->next = NULL;
}
return newNode;
}
```

One condition needs to be taken care of while creating a linked list and that is before head is created,which is first node in the list, there is no node present in list. This is special case in insert operation and needs extra care. Once, head node is inserted, other node can be insert before the head or after the head. This gives rise to two types of insertion operation on list that are:
1. Insertion at front of linked list

When node is inserted at front, next pointer of new node created is set to the present head pointer and head pointer is updated to new node.

```1. Create a node with data and next pointer as null
2. Change next pointer of new node to point to head.
3. Change head of list, now updated to new node.
```

Wrong and most common implementation

```void push(Node *head, int data){
Node * newNode  = (Node *)malloc(sizeof(Node));
newNode->data = data;
}
```

Above code suffers from a very basic problem which  can be stated as : Values assigned to local parameters of a function are never reflected in calling function. So instead of passing head pointer itself, pass pointer to head pointer, i.e. double pointer. So whatever is changed inside the function is also reflected back.

Correct implementation of insertion operation on linked list

```void push(Node **headRef, int data){
Node * newNode  = (Node *)malloc(sizeof(Node));
newNode->data = data;
}
```

2. Insertion at end or tail of linked list.
One way to insert a node at end of linked list to traverse entire list and find the last node, and then change next pointer of last node to point to newly created list.Code shown below:

```void insert_node_at_tail(Node **head,int value){
Node * newNode = createNode(value);

//If this is first node to be inserted
return;
}

//traverse till the end of list
while(current->next){
current = current->next;
}
current->next = newNode;
return;
}
```

When node is inserted at head, every time a new node is inserted, head pointer of linked list changes. Whereas when node is inserted at tail, one needs to scan the whole list in order to reach last node and insert new node. Scanning can be avoided if we can keep a tail pointer which points to current end node of list.

Code to insert at tail

```Node * createNode(int key){
Node * newNode  = (Node *)malloc(sizeof(Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}
void push_with_tail(Node *headRef, Node *tailRef, int key) {
Node * newNode  = NULL;
newNode = createNode(key);
//Special case to handle first node where head and tail are same.
*tail_ref = newNode
}
// else make next of tail pointer as new node and change the tail pointer.
else{
*tailRef->next  = newNode;
*tailRef = newNode;
}

}
```

There is another method with which we can insert a node, that is using local reference to last node, it is same as head reference, only thing is it stores pointer to the last nodes pointer. Below code implements insert operation using local reference to tail.

```#include <stdio.h>
#include <stdlib.h>
typedef struct node{
int data;
struct node *next;
}Node;

Node * newNode  = (Node *)malloc(sizeof(Node));
newNode->data = key;
}

int main(){
push(localRef, 3);

localRef = &((*localRef)->next);
push(localRef, 4);

localRef = &((*localRef)->next);
push(localRef, 5);

return 0;
}
```

After understanding the basic definition of linked list, let’s move on to second problem on it, that is how to traverse a linked list. For traversing a linked list, all we need is head pointer.
Take another temporary pointer called as current, assign head to it. Now while current is not NULL, print current node’s data and move current to current’s next. Once current becomes NULL, complete list has been traversed.

```void traverseList(Node *head){
while(current){
printf("%d", current->data);
current = current->next;
}
}
```

In the code above current start with head and ends at NULL, this pointer is automatically returned back to heap once function is executed as it is local variable or in an auto variable.
Condition of while loop automatically takes care of condition if the list is NULL, in that case head will be NULL and loop will never be executed. Most important step of traversal is to advance the current pointer to next pointer, most of the infinite loops are result of missing this step.

Next problem on linked list which is commonly asked in interviews is to delete a node from linked list.
To find the node to be deleted, we can traverse the list and compare each node with value to be deleted, once the node is found, what next? To delete a node, we need to connect the previous of current node to next of current node.

But there is no way we can now current node’s previous.  That means we need to traverse with two nodes, one current and other previous which just one node behind current. Initially current is set to head and previous to NULL, before moving current to current’ next next, previous is set to current node. When node to be deleted is found, previous will be just one node behind, and we can link previous’s next to current’s next as

`prev->next = current->next`

Complete code to delete a node from linked list is

```void deleteNode(Node **headRef, int key){
if(!(*headRef)) return; // If the list is empty

}

Node * prev = NULL;

while(current && current->data != key){
prev = current;
current = current->next;

}
// To check if element is present in list
if (current){
prev->next = current->next;
free(current);
}
}
```

There is another interesting variant of this problem, where node’s pointer is given and not the value. If interested, please read through this post : Delete a node from linked list
In this post we learnt basic linked list opearations, how to insert a node, delete a node from it and how to traverse a linked list. In following posts, we will solve some more problems on linked list.